１. 学会の概要
本学会は，SIAMの線形代数に関するActivity Groupが主催し，３年に１回開催され る。講演のテーマは線形計算をはじめとして，線形不等式論，線形システム論，画像 処理や文書検索などの応用に至るまで，線形代数のあらゆる分野にわたる。参加者の 多くは米国内から来ており，線形計算の分野の主要な研究者はほとんど参加している ようであった。講演は４つのパラレルセッションで行われ，全体で200件程度の発表 があった。
２. 興味深かった講演
今回聴講した講演のうち，興味深かったものに関するメモを以下にまとめる。なお， 今後発行予定のProceedingsには各講演について10ページ程度の論文が載る予定であ る。
(1) Fast and Accurate Linear Algebra on Totally Positive Matrices
Plamen S. Koev, Massachusetts Institution of Technology
すべての小行列式が正である正方行列をtotally positive matrixと呼ぶ。本発表で
は，Hilbert行列，Vandermonde行列，Cauchy行列などの特別な構造を持つ行列に対
し，totally positiveである場合に高い相対精度で固有値，特異値等が計算できるア
ルゴリズムを提案した。このためには，totally positive matrixが二重対角行列の
積として表現できること（Neville eliminationによる）を利用し，行列計算アルゴ
リズムを構成するすべての初等変換をこの二重対角行列に対して適用する。数値実験
の結果，条件数が10^160にも上るHilbert行列の最小固有値，最大固有値が両方とも
高い精度で計算できることが示された。詳しい論文等については
http://math.mit.edu/~plamen を参照。
(2) Superlinear Convergence of Krylov Subspace Methods
Valeria Simoncini, Universita di Bologna and Daniel B. Szyld, Temple
University
クリロフ部分空間法の超一次収束を説明する新しい解析モデルを提案。計算誤差があ
る場合の不完全なクリロフ部分空間法を扱えること，対角化不可能な行列の場合も扱
えることが特徴。数値実験により，GMRES法の収束特性を精度良く再現できることを
示した。SIAM Journal on Matrix Analysis and Applicationsに掲載予定。
(3) Large-scale eigenvalue problems
Rich Lehoucq, Sandia National Laboratories
大規模構造解析のための固有値解析手法であるAutomated-MultiLevel
Substructuring法の紹介。数千万元以上の問題に対し，下から100個以上の固有値・
固有ベクトルを求めることを目的とする。従来，このような目的のためにはブロック
Lanczos法がよく用いられていたが，その中で（Shift-and-Invertのために）使われ
る疎行列直接解法が超並列機上で高い並列化効率を得にくいという問題点があった。
本研究では，解析領域を複数の部品に分け，それぞれの固有モードと部品間の界面の
モードとを求めてそれらをうまく合成することにより，全体の固有モードを計算す
る。本手法により13.5M自由度の問題を解く場合，HP9000で３日以下の時間で済ん
だ。論文をSIAM Journal on Scientific Computingに投稿中とのこと。なお，発表者
のLehoucqはARPACKの開発者として，Implicit Restarted Arnoldi法に関する論文を
多数執筆している。
(4) Smoothed analysis of numerical algorithms
Shanghua Teng, Boston University & Akamai technologies
線形計算アルゴリズムの誤差（あるいは計算量）解析を行う方法として，worst-case
analysisとaverage-case analysisの２つの方法が従来から使われてきた。しかし，
前者は多くの実問題におけるアルゴリズムの振る舞いと比べ，誤差（あるいは計算
量）を悪く見積もりすぎるという欠点がある。一方，後者は，平均を取るのに使う問
題の確率分布が，実問題における分布と同じとは限らないという問題点がある。本発
表で提案するsmoothed analysisでは，たとえば誤差を調べる場合，各入力xに対し
て，その周りの微小なゆらぎについて誤差の平均を取り，その上でそれをxについて
最大化する。すなわち，Max_x Avg_r T(x+εr)を計算して誤差の指標とする。本アイ
ディアに基づくガウス消去法でのGrowth Factorの評価などが示された。
(5) Superfast Nested Dissection
Ming Gu, University of California, Berkeley
Nested Dissectionを用いた直接解法は，n×nの２次元格子に対する連立一次方程式
をO(n^3)の計算量で解くことができ，計算量の意味で最適な解法として知られてい
る。本発表では，直接法の計算において近似を許すことにより，誤差を指定するある
パラメータをpとしたとき，計算量をO(n^2p)にまで削減できることを示した。なお，
UCSBのShivkumar Chandrasekaranも，Guの共同研究者として連立一次方程式の超高速
解法に関する発表を行っていた。
(6) Linear Algebra in Quantum Computing
George Cybenko, Thayer School of Engineering, Dartmouth College
量子計算の基本的な考え方を，線形代数の言葉を使って説明。nビットの量子計算に
おいては，状態空間は2^n次元となり，計算アルゴリズムはこの空間における線形作
用素として表される。基本的な線形作用素として，２要素の交換，否定などの量子
ゲートと呼ばれる作用素が導入され，チューリングマシンで行えるすべての計算は，
これらの量子ゲートの組み合わせで計算できること（量子計算における表現定理）が
示された。しかし，一般には，nビットの量子計算を行うのに必要な量子ゲートの数
はnのべき乗で増大する。このゲート数を多項式オーダーに減らすための体系的方法
の開発（logic minimization problem）が今後の課題として示された。
(7) An introduction to Markov-based information retrieval systems
Amy N. Langville, North Carolina State University
Googleなどで使われている，マルコフ連鎖を使ったウェブ検索の基本的な手法の紹
介。本手法では，各ウェブページiに対し，ページの重要性を表すページランクx_iと
呼ばれる量が定義される。ページランクは，そのページをリンクしているページの
ページランク（ただしリンク元のページの全リンク数で割って規格化したもの）の合
計として計算される。ページランクを決める方程式は連立一次方程式となるが，これ
はマルコフ連鎖の遷移行列の固有値１に対する固有ベクトルを求める問題とみなすこ
とができ，べき乗法で解ける。今後の課題として，ウェブページ集合中に存在するク
ラスタ構造を抽出し，それを用いて計算を効率すること，べき乗法をより効率の良い
方法で置き換えること，リンク構造が変化した場合のページランクの更新を少ない計
算量で行うアルゴリズムの開発などが挙げられた。
学会出張報告のページに戻る
Topに戻る