ランダム行列と固有ベクトルのアンダーソン局在化

全文

(1)Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. ランダム行列と固有ベクトルのアンダーソン局在化村上弘1,a). 概要：大規模な行列が 3 重対角あるいは幅の狭い帯行列で，行列要素の値に乱雑性があると固有ベクトルに局在化が生じる．局在化したベクトルは，添字がある狭い区間の外部に在る要素の値は小さく無視できる．この現象は固体物性科学の分野では以前から「アンダーソン局在」として良く知られている．この現象の行列固有値問題の解法への応用を考察する．キーワード：アンダーソン，局在化，ランダム行列，固有ベクトル. Random Matrices and Anderson’s Localication of Eigenvectors Hiroshi Murakami1,a). Abstract: When a large size matrix is tridiagonal or narrow banded and also the matrix contain randomness in the elements, eigenvectors of the matrix are localized. Those elements of a localized vector are small and negligible in values whose induces are outside of a certain narrow interval. This phenomenon has long been known well in the ﬁeld of material science of solids as “Anderson’s localization”. We consider applications of this phenomenon to the solution method of matrix eigenproblems. Keywords: Anderson, Localization, Random matrix, Eigenvector. 1. はじめに固体物性論の分野で Anderson P. W. による Anderson. は局在化」していると言う．（グラフ上の隣接関係による距離で，ある点から少し離れた場所に対応する添字を持つベクトルの要素の値が微小で無視できる）．. 転移（局在）の現象が知られている（1977 年の Nobel 物理. Anderson モデルは隣接相互作用を持つ格子／ネットワー. 学賞 [3]）．物性の理論研究には大規模行列の数値対角化が. クの...(省略)．スケーリング理論によると Anderson モデ. よく用いられている．しかし「数値解析，数値解法」分野. ルでは，空間が 1 次元，2 次元の低次元系では（系の大き. ではこれまで Anderson 局在の現象と行列固有値計算の解. さが無限大の極限では）「ランダム性の程度によらず」に. 法との関係性はあまり意識されていないように思える．. すべての固有状態が局在化する．そうして 3 次元系では非. 局在化の実験例を紹介し，固有値問題で局在化が生じている解の高速な計算法の可能性などについて検討考察をしてみたい．. 2. 導入. 局在状態の発生はランダム性の程度に依存する（Anderson 転移）．これを行列の固有値問題に対応して考えると，3 重対角行列は隣接相互作用モデルの 1 次元系の場合に相当し，行列が大規模になるとき要素にランダム性があれば固有ベク. 大規模なベクトルが，ある狭い区間の外にある添字に対. トルは局在化する（無限系に近い大規模な行列で局在化）．. しては要素の値が微小で無視できるとき「ベクトル（状態）. 局在化した固有ベクトルの要素の値は，局在の中心から. 1. a). 首都大学東京・数理情報科学専攻 Department of Mathematics and Information Sciences, Tokyo Metropolitan University [email protected]. ⓒ 2015 Information Processing Society of Japan. 添字が離れると（ある尺度で）指数関数的な減少をする．数値解析の教科書では，ランダム性を持つ 3 重対角（帯）行列の固有ベクトルが局在化するという性質を取り上げた. 1.

(2) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. ものを見かけない．. 1. 実対称帯行列の典型例である 1 次元ラプラシアンの等間固有ベクトルは添字に対し正弦波であり系全体に広がっているので，3 重対角あるいは帯である行列の固有ベクトルが局在化を起こすことは奇妙に思われるかもしれない．もしもスケーリング理論を信じると，たとえばラプラシアンを差分近似して得られる対称 3 重対角行列に対して摂. VALUE OF ELEMENT. 隔格子による 3 点差分近似による 3 重対角行列の場合は，. 0.5. 0. -0.5. 動をランダムに加えるとき，小さい摂動であっても行列次数 N を十分大きくしていくと固有ベクトルは必ず局在化を. -1. 起こして正弦波として系全体には拡がらないことになる．. 0. 2000. このことは数値計算の丸め誤差があたかもランダムな摂動. 4000 6000 INDEX OF ELEMENT. 8000. 10000. 図 1 最小側 7 個の固有値の固有ベクトルの要素の値. のようにみなせるとするならば，数値と演算の有効桁数を固定して計算の規模だけを拡大していくと，数値計算による解が数学的な解とは定性的に異なったもの（局在した波. 1. と正弦波）となる可能性を示唆する．（おそらく，行列次するが，摂動が弱ければ局在化を起こすには大きな次数 N が必要となるのであろう．摂動が強ければ局在化領域は狭いが，摂動が弱ければ局在化領域が拡がる傾向になることも言えるのではないだろうか．）. 3. 数値実験の例. VALUE OF ELEMENT. 数 N が小さくても摂動が強ければ固有ベクトルは局在化 0.5. 0. -0.5. 3.1 局在化現象の例次数 N = 10, 000 の対称 3 重対角行列の要素を区間. -1. [−0.5, 0.5] の一様乱数で与えて，固有ベクトルの局在化の様子を観察してみる．固有ベクトル v の k 番目の要素の値をると，k 番目の要素の値の 2-ノルムへの寄与を ρk ≡ vk 2 と N すると 1 = k=1 ρk である．そこで ρk ，k=1, 2, . . ., N は. N に比べて小さい値となる．次の図 1，図 2，図 3 は，固有値分布の最小側，中央付近，最大側それぞれの場合について 7 個の固有値と対応. 4000 6000 INDEX OF ELEMENT. 8000. 10000. 1. VALUE OF ELEMENT. 固有ベクトルが局在化していれば，「分布の半径」r は次数. 2000. 図 2 中央部 7 個の固有値の固有ベクトルの要素の値. vk としてそれが 2-ノルムで正規化された単位ベクトルとす. 離散値 1 から N に対する分布の割合であるかのように考え N ることができる．そこで「分布の中心」を c ≡ k=1 k ρk ， N 「分布の半径」を r ≡ { k=1 ( k − c )2 ρk }1/2 と定義する．. 0. 0.5. 0. -0.5. する固有ベクトルについて 7 種類の色を用いて，横軸に要素の添字を，縦軸に要素の値をとって折れ線でグラフをプロットしたものである．ただし各ベクトルのプロットでは要素の大きさの最大値を 1 に規格化し，そのとき要素の値の大きさが閾値 10εM ≈ 10−15 以下のところはプロットを. -1. 0. 2000. 4000. 6000. 8000. 10000. INDEX OF ELEMENT. 図 3 最大側 7 個の固有値の固有ベクトルの要素の値. 省いている．各固有ベクトルはきわめて狭い範囲に局在化していて，グラフからはまるで縦線が並んでいるように見える．. 次の図 4 から図 23 は，最大側固有値の固有ベクトル 20 個それぞれについて，横軸には要素の添字をとり，縦軸には要素の値をとってプロットしたグラフである．ただしベクトルは要素の大きさの最大値を 1 にスケールしてプロットし，スケールした値が閾値 10εM ≈ 10−15 以下の要素は. ⓒ 2015 Information Processing Society of Japan. 2.

(3) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. プロットから省いている．局在化により閾値を越える値を. 1. 持つ要素の添字は極めて狭い範囲に集中していることが確 VALUE OF ELEMENT. 認できる．. VALUE OF ELEMENT. 1. 0.5. 0.5. 0. -0.5. 0. -1 1270. 1280. 1290. 1300. 1310. 1320. INDEX OF ELEMENT. -0.5. 図 7 第 4 固有ベクトルの要素の値（N =10, 000，h=1）． -1 2330. 分布の中心 c=1, 289.9，分布の半径 r=0.80 2340. 2350. 2360. 2370. 2380. INDEX OF ELEMENT. 図 4 第 1 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=2, 358.3，分布の半径 r=1.16 1. VALUE OF ELEMENT. VALUE OF ELEMENT. 1. 0.5. 0. 0.5. 0. -0.5. -0.5. -1 8850 -1 2970. 2980. 2990 INDEX OF ELEMENT. 3000. 8860. 8870 8880 INDEX OF ELEMENT. 8890. 8900. 図 8 第 5 固有ベクトルの要素の値（N =10, 000，h=1）．. 3010. 分布の中心 c=8, 875.6，分布の半径 r=0.91. 図 5 第 2 固有ベクトルの要素の値（N =10, 000，h=1）．. 1. 1. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. 分布の中心 c=2, 985.0，分布の半径 r=0.77. 0. -0.5. -1 8030. 8040. 8050. 8060. 8070. 8080. 8090. INDEX OF ELEMENT. 図 6 第 3 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=8, 058.5，分布の半径 r=0.97. ⓒ 2015 Information Processing Society of Japan. 0. -0.5. -1 8070. 8080. 8090 8100 INDEX OF ELEMENT. 8110. 8120. 図 9 第 6 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=8, 092.6，分布の半径 r=0.74. 3.

(4) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 1. 1. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. IPSJ SIG Technical Report. 0. -0.5. -1 9410. 9420. 9430 9440 9450 INDEX OF ELEMENT. 9460. 0. -0.5. -1 9780. 9470. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. 1. 0. -0.5. 8250. -0.5. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. 1. 0. -0.5. 8720. 8730. 図 12 第 9 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=8, 700.7，分布の半径 r=1.20. ⓒ 2015 Information Processing Society of Japan. 3890 3900 INDEX OF ELEMENT. 3910. 3920. 分布の中心 c=3, 899.3，分布の半径 r=1.49. 1. 8700 8710 INDEX OF ELEMENT. 3880. 図 14 第 11 固有ベクトルの要素の値（N =10, 000，h=1）．. 分布の中心 c=8, 235.4，分布の半径 r=0.93. 8690. 9830. 0. -1 3870. 8260. 図 11 第 8 固有ベクトルの要素の値（N =10, 000，h=1）．. -1 8680. 9820. 分布の中心 c=9, 802.7，分布の半径 r=0.88. 1. 8240 INDEX OF ELEMENT. 9810. 図 13 第 10 固有ベクトルの要素の値（N =10, 000，h=1）．. 分布の中心 c=9, 441.7，分布の半径 r=1.02. 8230. 9800. INDEX OF ELEMENT. 図 10 第 7 固有ベクトルの要素の値（N =10, 000，h=1）．. -1 8220. 9790. 0. -0.5. -1 5390. 5400. 5410 5420 5430 INDEX OF ELEMENT. 5440. 5450. 図 15 第 12 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=5, 420.6，分布の半径 r=0.79. 4.

(5) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 1. 1. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. IPSJ SIG Technical Report. 0. -0.5. -1 9810. 9820. 9830 9840 9850 INDEX OF ELEMENT. 9860. 0. -0.5. -1 2730. 9870. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. 1. 0. -0.5. 1450. -0.5. 0.5. 0.5. VALUE OF ELEMENT. VALUE OF ELEMENT. 1. 0. -0.5. 1430. 1440. 図 18 第 15 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=1, 403.4，分布の半径 r=0.62. ⓒ 2015 Information Processing Society of Japan. 6860 6870 INDEX OF ELEMENT. 6880. 6890. 分布の中心 c=6, 861.3，分布の半径 r=0.65. 1. 1400 1410 1420 INDEX OF ELEMENT. 6850. 図 20 第 17 固有ベクトルの要素の値（N =10, 000，h=1）．. 分布の中心 c=1, 430.9，分布の半径 r=0.91. 1390. 2780. 0. -1 6840. 1460. 図 17 第 14 固有ベクトルの要素の値（N =10, 000，h=1）．. -1 1380. 2770. 分布の中心 c=2, 758.5, 分布の半径 r=0.86. 1. 1420 1430 1440 INDEX OF ELEMENT. 2760. 図 19 第 16 固有ベクトルの要素の値（N =10, 000，h=1）．. 分布の中心 c=9, 842.1，分布の半径 r=1.24. 1410. 2750. INDEX OF ELEMENT. 図 16 第 13 固有ベクトルの要素の値（N =10, 000，h=1）．. -1 1400. 2740. 0. -0.5. -1 4980. 4990. 5000 5010 INDEX OF ELEMENT. 5020. 5030. 図 21 第 18 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=5, 008.0，分布の半径 r=0.79. 5.

(6) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 1E0. 1. MAGNITUDE OF ELEMENT. VALUE OF ELEMENT. 1E-2 0.5. 0. -0.5. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14. -1 8920. 8930. 8940 8950 8960 INDEX OF ELEMENT. 8970. 2330. 8980. 2340. 2350 2360 INDEX OF ELEMENT. 2370. 2380. 図 24 第 1 固有ベクトルの要素（大きさの対数）. 図 22 第 19 固有ベクトルの要素の値（N =10, 000，h=1）．. 分布の中心 c=2, 358.3，分布の半径 r=1.16. 分布の中心 c=8, 948.7，分布の半径 r=1.15. 1E0. MAGNITUDE OF ELEMENT. 1E-2. 1E-6 1E-8 1E-10 1E-12 1E-14. 0.5. 2970. 2980. 2990. 3000. 3010. INDEX OF ELEMENT 0. 図 25 第 2 固有ベクトルの要素（大きさの対数）分布の中心 c=2, 985.0，分布の半径 r=0.77. -0.5. -1 6190. 6200. 6210 6220 6230 INDEX OF ELEMENT. 6240. 6250. 図 23 第 20 固有ベクトルの要素の値（N =10, 000，h=1）．分布の中心 c=6, 223.3，分布の半径 r=0.74. 次の図 24 から図 43 は，上記と同じ最大側固有値の固有ベクトル 20 個それぞれについて，横軸には要素の添字をとり，今度は縦軸を要素の値の大きさの「対数」でプロットしたグラフである．局在の中央から添字の位置が離れるときに要素の値が指数関数的に減少していることがわかる．. ⓒ 2015 Information Processing Society of Japan. 1E0 1E-2 MAGNITUDE OF ELEMENT. VALUE OF ELEMENT. 1. 1E-4. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14 8030. 8040. 8050 8060 8070 INDEX OF ELEMENT. 8080. 8090. 図 26 第 3 固有ベクトルの要素（大きさの対数）分布の中心 c=8, 058.5，分布の半径 r=0.97. 6.

(7) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 1E0. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. IPSJ SIG Technical Report. 1E-4 1E-6 1E-8 1E-10 1E-12. 1E-6 1E-8 1E-10 1E-12 1E-14. 1E-14 1270. 1E-4. 1280. 1290 1300 INDEX OF ELEMENT. 1310. 9410. 1320. 1E0. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. 9450. 9460. 9470. 分布の中心 c=9, 441.7，分布の半径 r=1.02. 1E-4 1E-6 1E-8 1E-10 1E-12. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14. 1E-14 8860. 8870 8880 INDEX OF ELEMENT. 8890. 8220. 8900. 図 28 第 5 固有ベクトルの要素（大きさの対数）. 8230. 8240 INDEX OF ELEMENT. 8250. 8260. 図 31 第 8 固有ベクトルの要素（大きさの対数）. 分布の中心 c=8, 875.6，分布の半径 r=0.91. 分布の中心 c=8, 235.4，分布の半径 r=0.93. 1E0. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. 9440. 図 30 第 7 固有ベクトルの要素（大きさの対数）. 分布の中心 c=1, 289.9，分布の半径 r=0.80. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14 8070. 9430. INDEX OF ELEMENT. 図 27 第 4 固有ベクトルの要素（大きさの対数）. 8850. 9420. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14. 8080. 8090 8100 INDEX OF ELEMENT. 8110. 図 29 第 6 固有ベクトルの要素（大きさの対数）分布の中心 c=8, 092.6，分布の半径 r=0.74. ⓒ 2015 Information Processing Society of Japan. 8120. 8680. 8690. 8700 8710 INDEX OF ELEMENT. 8720. 8730. 図 32 第 9 固有ベクトルの要素（大きさの対数）分布の中心 c=8, 700.7，分布の半径 r=1.20. 7.

(8) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 1E0. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. IPSJ SIG Technical Report. 1E-4 1E-6 1E-8 1E-10 1E-12. 9800 9810 INDEX OF ELEMENT. 9820. 1E-8 1E-10 1E-12. 9810. 9830. 9820. 9830. 9840. 9850. 9860. 図 33 第 10 固有ベクトルの要素（大きさの対数）. 図 36 第 13 固有ベクトルの要素（大きさの対数）. 分布の中心 c=9, 802.7，分布の半径 r=0.88. 分布の中心 c=9, 842.1，分布の半径 r=1.24. 1E0. 1E0. 1E-2. 1E-2. 1E-4 1E-6 1E-8 1E-10 1E-12. 3870. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14. 3880. 3890 3900 INDEX OF ELEMENT. 3910. 1400. 3920. 1410. 1420 1430 1440 INDEX OF ELEMENT. 1450. 図 34 第 11 固有ベクトルの要素（大きさの対数）. 図 37 第 14 固有ベクトルの要素（大きさの対数）. 分布の中心 c=3, 899.3，分布の半径 r=1.49. 分布の中心 c=1, 430.9，分布の半径 r=0.91. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. 1E0. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14 5390. 9870. INDEX OF ELEMENT. MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. 9790. 1E-14. MAGNITUDE OF ELEMENT. 1E-6. 1E-14. 1E-14 9780. 1E-4. 1460. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14. 5400. 5410 5420 5430 INDEX OF ELEMENT. 5440. 5450. 1380. 1390. 1400 1410 1420 INDEX OF ELEMENT. 1430. 図 35 第 12 固有ベクトルの要素（大きさの対数）. 図 38 第 15 固有ベクトルの要素（大きさの対数）. 分布の中心 c=5, 420.6，分布の半径 r=0.79. 分布の中心 c=1, 403.4，分布の半径 r=0.62. ⓒ 2015 Information Processing Society of Japan. 1440. 8.

(9) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 1E0. 1E0. 1E-2. 1E-2 MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. IPSJ SIG Technical Report. 1E-4 1E-6 1E-8 1E-10 1E-12. 1E-6 1E-8 1E-10 1E-12 1E-14. 1E-14 2730. 1E-4. 2740. 2750 2760 INDEX OF ELEMENT. 2770. 8920. 2780. 8930. 8940. 8950. 8960. 8970. 8980. INDEX OF ELEMENT. 図 39 第 16 固有ベクトルの要素（大きさの対数）. 図 42 第 19 固有ベクトルの要素（大きさの対数）. 分布の中心 c=2, 758.5，分布の半径 r=0.86. 分布の中心 c=8, 948.7，分布の半径 r=1.15. 1E0. 1E-4 1E-6 1E-8 1E-10. 1E0. 1E-12. 1E-2. 1E-14 6840. 6850. 6860 6870 INDEX OF ELEMENT. 6880. 6890. 図 40 第 17 固有ベクトルの要素（大きさの対数）分布の中心 c=6, 861.3，分布の半径 r=0.65. MAGNITUDE OF ELEMENT. MAGNITUDE OF ELEMENT. 1E-2. 1E-4 1E-6 1E-8 1E-10 1E-12 1E-14 6190. 1E0. 6210 6220 6230 INDEX OF ELEMENT. 6240. 6250. 図 43 第 20 固有ベクトルの要素（大きさの対数）. 1E-2 MAGNITUDE OF ELEMENT. 6200. 分布の中心 c=6, 223.3，分布の半径 r=0.74. 1E-4 1E-6 1E-8 1E-10 1E-12. この例では固有値が最大側から第 4, 636 番目の固有ベクトルが「分布の半径」が r = 11.04 で最大であった（図 92. 1E-14 4980. 4990. 5000 5010 INDEX OF ELEMENT. 5020. 図 41 第 18 固有ベクトルの要素（大きさの対数）分布の中心 c=5, 008.0，分布の半径 r=0.79. ⓒ 2015 Information Processing Society of Japan. 5030. 参照）．そのベクトルを添字の番号を横軸に，要素の値を縦軸にとってプロットしたグラフが図 44 で，要素の値の大きさの「対数」で縦軸をプロットしたグラフが図 45 である．. 9.

(10) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 10000 SUPPORT OF THE EIGENVECTOR. VALUE OF ELEMENT. 1. 0.5. 0. -0.5. -1 7500. 7510. 7520 7530 INDEX OF ELEMENT. 7540. 6000. 4000. 2000. 0. 7550. 図 44 「分布の半径」が最大の固有ベクトル 2 個. 8000. 0. 2000 4000 6000 8000 EIGENMODE REORDERED BY THE CENTER. 10000. 図 46 固有ベクトルの「分布の中心」に対する台； N =10, 000，h=1. 1E0. MAGNITUDE OF ELEMENT. 1E-2 1E-4. SUPPORT OF THE EIGENVECTOR. 10000. 1E-6. 8000. 6000. 4000. 2000. 0. 0. 1E-10. 2000. 4000. 6000. 8000. 10000. EIGENMODE REORDERED BY THE CENTER. 1E-8. 図 47 固有ベクトルの「分布の中心」に対する台； N =10, 000，h=2. 1E-12 1E-14 7460 7480 7500 7520 7540 7560 7580 7600 7620 7640 INDEX OF ELEMENT. 10000. 図 46 から図 49 は，次数 N = 10, 000 で半帯幅が h = 1，. 2，4，8 のそれぞれの場合について，横軸に固有ベクトルの「分布の中心」の位置順につけた番号をとり，縦軸には要素の絶対値が最大のものに対する比が「閾値」以上である添字の区間をとってプロットしたグラフである（ここの閾値は 10−12 と設定した）．帯幅が増すとき固有ベクトル. SUPPORT OF THE EIGENVECTOR. 図 45 「分布の半径」が最大の固有ベクトル 2 個（縦軸対数）. 8000. 6000. 4000. 2000. 0. 0. 2000 4000 6000 8000 EIGENMODE REORDERED BY THE CENTER. 10000. 図 48 固有ベクトルの「分布の中心」に対する台； N =10, 000，h=4. の局在領域の幅が拡がる様子がわかる．. ⓒ 2015 Information Processing Society of Japan. 10.

(11) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 10000. 18. SUPPORT OF THE EIGENVECTOR. 16 8000. 14 12 RADIUS. 6000. 4000. 10 8 6 4. 2000. 2 0. 0 0. 2000. 4000. 6000. 8000. 10000. 0. 200. EIGENMODE REORDERED BY THE CENTER. 400 600 CENTER. 800. 1000. 図 51 分布の中心と分布の半径; N =1, 000，h=2. 図 49 固有ベクトルの「分布の中心」に対する台； N =10, 000，h=8. 50 45 40 35. 次数 N の対称帯行列 B を各要素が区間 [−0.5, 0.5] で一様な乱数とするとき，半帯幅 h を変えて固有ベクトルの局. RADIUS. 3.2 帯幅と局在化. 30 25 20. 在化の状況を観察してみる．. 15. 3.2.1 行列次数が N = 1, 000 の場合. 10. 行列次数が N = 1, 000 の場合に，半帯幅を h = 1，2，4，. 5. 8 としたそれぞれの場合について，すべての固有ベクトル. 0. に対して横軸を「分布の中心」に縦軸を「分布の半径」とするグラフを図 50 から図 53 に示す．各図から「分布の. 0. 200. 400 600 CENTER. 800. 1000. 図 52 分布の中心と分布の半径; N =1, 000，h=4. 半径」の最大値は，h = 1 のとき 7.5 程度，h = 2 のとき. 18 程度，h = 4 のとき 50 程度，h = 8 のとき 190 程度であることがわかる．. 180 160 140. RADIUS. 120. 8. 80. 7. 60. 6. 40 20. 5 RADIUS. 100. 0. 4 3. 200. 400 600 CENTER. 800. 1000. 図 53 分布の中心と分布の半径; N =1, 000，h=8. 2 1 0. 0. 同様に，h = 1，2，4，8 としたそれぞれの場合につい 0. 200. 400. 600. 800. CENTER. 図 50 分布の中心と分布の半径; N =1, 000，h=1. ⓒ 2015 Information Processing Society of Japan. 1000. て，すべての固有ベクトルに対する「分布の半径」とその累積度数をプロットしたグラフを図 54 から図 57 に示す．さらにそれらを 1 枚の図にまとめたものが図 58 であり，. 11.

(12) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 横軸の「分布の半径」を対数でプロットした図が図 59 で. 1000 CUMULATIVE FREQUENCY. ある．. CUMULATIVE FREQUENCY. 1000. 800. 600. 400. 800. 600. 400. 200. 0 0. 50. 100. 200. 150. 200. 250. RADIUS. 図 57 「分布の半径」とその累積度数; N =1, 000，h=8. 0 0. 2. 4. 6. 8. 10. 12. RADIUS. 図 54 「分布の半径」とその累積度数; N =1, 000，h=1. CUMULATIVE FREQUENCY. 1000 CUMULATIVE FREQUENCY. 1000. 800. 800. 600. 400. 200. h=1 h=2 h=4 h=8. 600. 0 400. 0. 200. 20. 40 RADIUS. 60. 80. 100. 図 58 「分布の半径」とその累積度数; N =1, 000，h=1，2，4，8. 0 0. 5. 10. 15 20 RADIUS. 25. 30. 1000 CUMULATIVE FREQUENCY. 図 55 「分布の半径」とその累積度数; N =1, 000，h=2. CUMULATIVE FREQUENCY. 1000. 800. 600. 800. 600. 400. 200. h=1 h=2 h=4 h=8. 0 0.1. 400. 1. 10 RADIUS. 100. 1000. 図 59 「分布の半径」（対数）とその累積度数; N =1, 000，h=1，2，. 200. 4，8. 0 0. 10. 20. 30. 40. 50. 60. 70. 80. 90. RADIUS. 図 56 「分布の半径」とその累積度数; N =1, 000，h=4. ⓒ 2015 Information Processing Society of Japan. 固有ベクトルを固有値の順に並べてみると，固有値が最大と最小の付近では固有ベクトルの「分布の半径」が小さくなる傾向のあることが図 60 から図 63 からわかる．. 12.

(13) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 8. 180. 7. 160 140. 6. 120 RADIUS. RADIUS. 5 4. 100 80. 3. 60. 2. 40. 1 0. 20 0. 200. 400 600 EIGENMODE. 800. 0. 1000. 0. 200. 400. 600. 800. 1000. EIGENMODE. 図 60 固有値の順に並べた「分布の半径」; N =1, 000，h=1. 図 63 固有値の順に並べた「分布の半径」; N =1, 000，h=8. 18 16 14. 3.2.2 行列次数が N = 3, 000 の場合. RADIUS. 12. 行列次数が N = 3, 000 の場合に，半帯幅を h = 1，2，4，. 10. 8 としたそれぞれの場合について，すべての固有ベクトル. 8. に対して横軸を「分布の中心」に縦軸を「分布の半径」と. 6. するグラフを図 64 から図 67 に示す．各図から「分布の. 4. 半径」の最大値は，h = 1 のとき 7.5 程度，h = 2 のとき. 2. 30 程度，h = 4 のとき 65 程度，h = 8 のとき 230 程度で. 0. 0. 200. 400 600 EIGENMODE. 800. 1000. あることがわかる．. 図 61 固有値の順に並べた「分布の半径」; N =1, 000，h=2. 50. 8. 45. 7. 40. 6 5. 30. RADIUS. RADIUS. 35. 25 20. 3. 15. 2. 10. 1. 5 0. 4. 0. 200. 400. 600. 800. 1000. EIGENMODE. 図 62 固有値の順に並べた「分布の半径」; N =1, 000，h=4. ⓒ 2015 Information Processing Society of Japan. 0. 0. 600. 1200 1800 CENTER. 2400. 3000. 図 64 分布の中心と分布の半径; N =3, 000，h=1. 13.

(14) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 横軸の「分布の半径」を対数でプロットした図が図 73 で. 30. ある． 25. 3000 15 10 5 0. 0. 600. 1200 1800 CENTER. 2400. 3000. CUMULATIVE FREQUENCY. RADIUS. 20. 図 65 分布の中心と分布の半径; N =3, 000，h=2. 2500 2000 1500 1000 500 0 0. 2. 4. 6. 8. 10. 12. RADIUS 70. 図 68 「分布の半径」とその累積度数; N =3, 000，h=1. 60. 40. 3000 30 20 10 0. 0. 600. 1200 1800 CENTER. 2400. 3000. 図 66 分布の中心と分布の半径; N =3, 000，h=4. CUMULATIVE FREQUENCY. RADIUS. 50. 2500 2000 1500 1000 500 0 0. 5. 10. 250. 15 20 RADIUS. 25. 30. 図 69 「分布の半径」とその累積度数; N =3, 000，h=2. 150. 3000. 100. 50. 0. 0. 600. 1200 1800 CENTER. 2400. 3000. 図 67 分布の中心と分布の半径; N =3, 000，h=8. 同様に，h = 1，2，4，8 としたそれぞれの場合について，すべての固有ベクトルに対する「分布の半径」とその累積度数をプロットしたグラフを図 68 から図 71 に示す．さらにそれらを 1 枚の図にまとめたものが図 72 であり， ⓒ 2015 Information Processing Society of Japan. CUMULATIVE FREQUENCY. RADIUS. 200. 2500 2000 1500 1000 500 0 0. 10. 20. 30. 40 50 RADIUS. 60. 70. 80. 90. 図 70 「分布の半径」とその累積度数; N =3, 000，h=4. 14.

(15) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. やして h = 5，10，20，40，80 とすると，図 74 から図 78. CUMULATIVE FREQUENCY. 3000. のグラフにみるように「分布の半径」は増大して最大値は. h = 5 では 100 程度，h = 10 では 250 程度，h = 20 では. 2500. 850 程度，h = 40 では 1, 100 程度，h = 80 では 1100 程度. 2000. となりしだいに N = 3, 000 に対して「分布の半径」が小さ. 1500. いとはいえなくなる．. 1000. 110 100. 500. 90 0. 80 50. 100. 150 RADIUS. 200. 70. 250. 図 71 「分布の半径」とその累積度数; N =3, 000，h=8. RADIUS. 0. 60 50 40 30 20. 3000. 10 0. 600. 1200. 1800. 2400. 3000. CENTER 2000. 図 74 分布の中心と分布の半径; N =3, 000，h=5. 1500. 300. 1000 500. h=1 h=2 h=4 h=8. 0 0. 20. 40 RADIUS. 60. 80. 250 200 100. 図 72 「分布の半径」とその累積度数; N =3, 000，h=1，2，4，8. RADIUS. CUMULATIVE FREQUENCY. 0 2500. 150 100 50. 3000 2500. 0. 600. 1200. 1800. 2400. 3000. CENTER. 図 75 分布の中心と分布の半径; N =3, 000，h=10. 2000 1500. 900. 1000. 800 500. h=1 h=2 h=4 h=8. 0 0.1. 1. 10. 100. 700 600 1000. RADIUS. 図 73 「分布の半径」（対数）とその累積度数; N =3, 000，h=1，2，. 4，8. ここまで，「分布の半径」の対数を横軸に累積度数を縦軸にとったグラフは h が違っても相似的な形をしていて，「分布の半径」の累積頻度は半帯幅の約 3/2 乗にほぼ比例していた．しかし N を固定したまま半帯幅 h をさらに増 ⓒ 2015 Information Processing Society of Japan. RADIUS. CUMULATIVE FREQUENCY. 0. 500 400 300 200 100 0. 0. 600. 1200 1800 CENTER. 2400. 3000. 図 76 分布の中心と分布の半径; N =3, 000，h=20. 15.

(16) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 1200. 3000 CUMULATIVE FREQUENCY. 1000. RADIUS. 800 600 400 200 0. 2500 2000 1500 1000 500 0. 0. 600. 1200 1800 CENTER. 2400. 0. 3000. 50. 100. 150. 200. 250. 300. RADIUS. 図 80 「分布の半径」とその累積度数; N =3, 000，h=10. 図 77 分布の中心と分布の半径; N =3, 000，h=40. 1200 1000. 3000. 600 400 200 0. 0. 600. 1200 1800 CENTER. 2400. 3000. CUMULATIVE FREQUENCY. RADIUS. 800. 図 78 分布の中心と分布の半径; N =3, 000，h=80. 2500 2000 1500 1000 500 0 0. 100. 200. h = 5，10，20，40，80 に対する「分布の半径の」累積度数のグラフを図 79 から図 83 に示す．それらを 1 枚に. 300. 400 500 600 RADIUS. 700. 800. 900. 図 81 「分布の半径」とその累積度数; N =3, 000，h=20. まとめたグラフを図 84 にその横軸を対数プロットにしたグラフを図 85 に示す．半帯幅 h が小さかった図 73 の場合とは異なり，図 85 ではグラフの形状が h に依存して変. 3000. 3000. 2500. 2500. CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 化していて相似的ではないことがわかる．. 2000 1500 1000 500 0. 2000 1500 1000 500 0. 0. 20. 40. 60 RADIUS. 80. 100. 120. 図 79 「分布の半径」とその累積度数; N =3, 000，h=5. ⓒ 2015 Information Processing Society of Japan. 0. 500. 1000. 1500 RADIUS. 2000. 2500. 図 82 「分布の半径」とその累積度数; N =3, 000，h=40. 16.

(17) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 3.2.3 行列次数が N = 10, 000 の場合. CUMULATIVE FREQUENCY. 3000. 行列次数を N = 10, 000 として，半帯幅を h = 1，2，4，. 8 としたそれぞれの場合について，すべての固有ベクトル. 2500. に対して「分布の半径」とその累積度数をプロットしたグ. 2000. ラフを図 86 から図 89 に示す．さらにそれらを 1 枚の図にまとめたものが図 90 であり，横軸の「分布の半径」を. 1500. 対数でプロットしたグラフが図 91 である．. 1000 500 0 0. 1000. 2000. 3000 4000 RADIUS. 5000. 6000. 7000. 図 83 「分布の半径」とその累積度数; N =3, 000，h=80. CUMULATIVE FREQUENCY. 3000 CUMULATIVE FREQUENCY. 10000. 2500. 8000. 6000. 4000. 2000. 2000. 0 1500. 0. 2. 4. 6. 8. 10. 12. RADIUS. 1000. 図 86 「分布の半径」とその累積度数; N =10, 000，h=1. h=5 h=10 h=20 h=40 h=80. 500 0 0. 200. 400. 600. 800. 1000. RADIUS. 図 84 「分布の半径」とその累積度数; N =3, 000，h=5，10，20，. 40，80. h=5 h=10 h=20 h=40 h=80. 2500. 10000 CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 3000. 2000 1500 1000 500. 8000. 6000. 4000. 2000. 0 1. 10. 100 RADIUS. 1000. 図 85 「分布の半径」（対数）とその累積度数; N =3, 000，h=5，. 10，20，40，80. ⓒ 2015 Information Processing Society of Japan. 0 0. 5. 10. 15 20 RADIUS. 25. 30. 図 87 「分布の半径」とその累積度数; N =10, 000，h=2. 17.

(18) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 10000 CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 10000. 8000. 6000. 4000. 2000. 8000. 6000. 4000. 2000. h=1 h=2 h=4 h=8. 0. 0 0. 10. 20. 30. 40 50 RADIUS. 60. 70. 80. 0.1. 90. 1. 10. 100. 1000. RADIUS. 図 88 「分布の半径」とその累積度数; N =10, 000，h=4. 図 91 「分布の半径」（対数）とその累積度数; N =10, 000，h=1，. 2，4，8. CUMULATIVE FREQUENCY. 10000. 8000. 同様に，次数 N = 10, 000 で半帯幅 h = 1，2，4，8 に. 6000. 対して縦軸にすべての固有ベクトルの固有値を減少順に並べて付けた順番を，縦軸に「分布の半径」をとってプロッ. 4000. トしたものをそれぞれ図 92 から図 95 に示す．各図から「分布の半径」の最大値は h = 1 では 11 程度，h = 2 では. 2000. 30 程度，h = 4 では 80 程度，h = 8 では 260 程度である 0 0. 50. 100. 150 RADIUS. 200. ことがわかる．. 250. 図 89 「分布の半径」とその累積度数; N =10, 000，h=8. 12. 10000. 8 6000. RADIUS. CUMULATIVE FREQUENCY. 10 8000. 4000. 6 4. 2000. h=1 h=2 h=4 h=8. 0 0. 20. 40 RADIUS. 60. 80. 2 0 100. 図 90 「分布の半径」とその累積度数; N =10, 000，h=1，2，4，8. ⓒ 2015 Information Processing Society of Japan. 0. 2000. 4000. 6000. 8000. 10000. EIGENMODE. 図 92 固有値の順に並べた「分布の半径」; N =10, 000，h=1. 18.

(19) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. ラフを図 96 から図 99 に示す．さらにそれらを 1 枚の図. 30. にまとめたものが図 100 であり，横軸の「分布の半径」を 25. 対数でプロットしたグラフが図 101 である．. 30000. 15 10 5 0. 0. 2000. 4000 6000 EIGENMODE. 8000. 10000. 図 93 固有値の順に並べた「分布の半径」; N =10, 000，h=2. CUMULATIVE FREQUENCY. RADIUS. 20. 25000 20000 15000 10000 5000 0 0. 2. 4. 6. 8. 10. 12. RADIUS. 80. 図 96 「分布の半径」とその累積度数; N =30, 000，h=1. 70 60. RADIUS. 50 40. 30000. 20 10 0. 0. 2000. 4000 6000 EIGENMODE. 8000. 10000. 図 94 固有値の順に並べた「分布の半径」; N =10, 000，h=4. CUMULATIVE FREQUENCY. 30. 25000 20000 15000 10000 5000 0 0. 300. 5. 10. 15 20 RADIUS. 25. 30. 図 97 「分布の半径」とその累積度数; N =30, 000，h=2. 250. RADIUS. 200 150. 30000. 50 0. 0. 2000. 4000 6000 EIGENMODE. 8000. 10000. 図 95 固有値の順に並べた「分布の半径」; N =10, 000，h=8. 3.2.4 行列次数が N = 30, 000 の場合行列次数を N = 30, 000 として，半帯幅を h = 1，2，4，. 8 としたそれぞれの場合について，すべての固有ベクトルに対して「分布の半径」とその累積度数をプロットしたグ. ⓒ 2015 Information Processing Society of Japan. CUMULATIVE FREQUENCY. 100. 25000 20000 15000 10000 5000 0 0. 10. 20. 30. 40 50 RADIUS. 60. 70. 80. 90. 図 98 「分布の半径」とその累積度数; N =30, 000，h=4. 19.

(20) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 3.2.5 行列次数が N = 100, 000 の場合. CUMULATIVE FREQUENCY. 30000. 行列次数を N = 100, 000 として，半帯幅を h = 1，2，. 4，8 としたそれぞれの場合について，すべての固有ベクト. 25000. ルに対して「分布の半径」とその累積度数をプロットした. 20000. グラフを図 102 から図 105 に示す．さらにそれらを 1 枚の図にまとめたものが図 106 であり，横軸の「分布の半. 15000. 径」を対数でプロットしたグラフが図 107 である．. 10000 5000 0 0. 50. 100. 150 RADIUS. 200. 250. 図 99 「分布の半径」とその累積度数; N =30, 000，h=8. CUMULATIVE FREQUENCY. 30000 CUMULATIVE FREQUENCY. 100000. 25000. 80000. 60000. 40000. 20000. 20000. 0 15000. 0. 2. 4. 6. 8. 10. 12. RADIUS. 10000. 図 102 「分布の半径」とその累積度数; N =100, 000，h=1 5000. h=1 h=2 h=4 h=8. 0 0. 20. 40 RADIUS. 60. 80. 100. 図 100 「分布の半径」とその累積度数; N =30, 000，h=1，2，4，. 8. 30000. CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 100000 25000 20000 15000 10000 5000. h=1 h=2 h=4 h=8. 0 0.1. 1. 10 RADIUS. 100. 1000. 図 101 「分布の半径」（対数）とその累積度数; N =30, 000，h=1，. 2，4，8. ⓒ 2015 Information Processing Society of Japan. 80000. 60000. 40000. 20000. 0 0. 5. 10. 15 20 RADIUS. 25. 30. 図 103 「分布の半径」とその累積度数; N =100, 000，h=2. 20.

(21) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 100000 CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 100000. 80000. 60000. 40000. 20000. 80000. 60000. 40000. 20000. h=1 h=2 h=4 h=8. 0. 0 0. 10. 20. 30. 40 50 RADIUS. 60. 70. 80. 0.1. 90. 1. 10. 100. 1000. RADIUS. 図 104 「分布の半径」とその累積度数; N =100, 000，h=4. 図 107 「分布の半径」(対数) とその累積度数; N =100, 000，h=1，. 2，4，8. CUMULATIVE FREQUENCY. 100000. 80000. 60000. 3.2.6 行列次数が N = 300, 000 の場合. 40000. としたそれぞれの場合について，すべての固有ベクトルに. 行列次数を N = 300, 000 として，半帯幅を h = 1，2，4 対して「分布の半径」とその累積度数をプロットしたグラ. 20000. フを図 108 から図 110 に示す．さらにそれらを 1 枚の図にまとめたものが図 111 であり，横軸の「分布の半径」を. 0 0. 50. 100. 150 RADIUS. 200. 対数でプロットしたグラフが図 112 である．. 250. 図 105 「分布の半径」とその累積度数; N =100, 000，h=8. 100000. 80000 CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. 300000. 60000. 40000. 20000. h=1 h=2 h=4 h=8. 0 0. 20. 40. 60. 80. 100. RADIUS. 図 106 「分布の半径」とその累積度数; N =100, 000，h=1，2，4，. 8. ⓒ 2015 Information Processing Society of Japan. 250000 200000 150000 100000 50000 0 0. 2. 4. 6 RADIUS. 8. 10. 12. 図 108 「分布の半径」とその累積度数; N =300, 000，h=1. 21.

(22) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告. 300000. 300000. 250000. 250000. CUMULATIVE FREQUENCY. CUMULATIVE FREQUENCY. IPSJ SIG Technical Report. 200000 150000 100000 50000. 200000 150000 100000 50000 h=1 h=2 h=4. 0. 0 0. 5. 10. 15 20 RADIUS. 25. 0.1. 30. 1. 10. 100. 1000. RADIUS. 図 109 「分布の半径」とその累積度数; N =300, 000，h=2. 図 112 「分布の半径」（対数）とその累積度数; N =300, 000，h=1，. 2，4. 3.3 帯固有値問題の解法について次数 N で半帯幅 h の対称帯行列 B の近似固有対をすべて求めるのには，村田の方法（文献 [18]）を用いた（この. CUMULATIVE FREQUENCY. 300000. 方法は本来は，必要な範囲の固有値を持つごく一部の固有対だけを求めるためのものである）．具体的には以下のよ. 250000. うにした． 200000. ( 1 ) 帯行列 B を村田ハウスホルダ法で対称 3 重対角行列 T に変換する（TRIDIA）．. 150000. ( 2 ) T のすべての固有値をスツルム 2 分法で精密に求める. 100000. （BISECT）．. ( 3 ) 求めた固有値の分だけ B を対角シフトした帯行列か. 50000. ら片側ピボット選択付き帯 LU 分解による逆反復法で. 0 0. 10. 20. 30. 40 50 RADIUS. 60. 70. 80. 固有ベクトルを求める．その際に固有値の近接度によ. 90. る選択的再直交化付き逆反復法を行う（INVITR）．. 図 110 「分布の半径」とその累積度数; N =300, 000，h=4. ただし，次数 N が 1 万を越えた場合には主記憶容量の制約と計算時間が長くなることから選択的再直交化の部分を省略した．実験に用いた計算機システムの諸元は以下のものである（表 1）．ただし計算には CPU コア 2 個のうちの 1 個だけを用いた．. 300000 CUMULATIVE FREQUENCY. 表 1 Intel Core2 Duo E6600 のシステムの諸元 250000. CPU：Intel Core2 Duo E6600 2.4GHz （2 コア，最外キャッシュ L2 は 4Mbytes）. 200000. コアあたり SSSE3 でピーク性能 9.6GFLOPS（DP）主記憶：2Gbytes（Dual-Channel，PC2-6400）. 150000. OS：Fedora 7 for x86 64 100000. コンパイラ：Intel Fortran version 10.0 for Linux. 50000 h=1 h=2 h=4. 0 0. 20. 40. 60. 80. この計算機システムは現時点ではかなり古いもの（CPU 100. RADIUS. 図 111 「分布の半径」とその累積度数; N =300, 000，h=1，2，4，. 8. ⓒ 2015 Information Processing Society of Japan. は 2006 年第 3 四半期に発表）であるが，その 8 年後の以下の諸元を持つ比較的最近（CPU は 2014 年第 3 四半期に発表）のシステム（表 2）を用いて同様に 1 コアだけ用いてみたところ，2 倍から 3 倍程度高速に計算できた．. 22.

(23) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report 表 2 Intel Corei7-5960X のシステムの諸元. 表 6 経過時間（秒）：（次数 N =30, 000，半帯幅 h）. h. TRIDIA. BISECT. 1. —. 546. 143. 2. 57.4. 530. 218. OS：CentOS 7.0 for x86 64. 4. 50.1. 511. 364. コンパイラ：Intel Fortran version 15.0.0 for Linux. 8. 63.3. 498. 862. CPU：Corei7-5960X 3.0GHz （8 コア，最外キャッシュ L3 は 20MB，. Turbo-boost，Hyper-Thread オフ）コアあたり AVX2 でピーク性能 48GFLOPS（DP）主記憶：64Gbytes（Quad-Channel，PC4-12800）. INVITR 再直交化無し. 両システムの 1 コアあたりの倍精度演算の理論上限性能はそれぞれ 9.6GFLOPS と 48GFLOPS（AVX2 が使える場合．AVX までなら 24GFLOPS，SSE4.2 では 12GFLOPS）. 表 7 経過時間（秒）：（次数 N =100, 000，半帯幅 h）. h. TRIDIA. BISECT. 電気信号レベルでのメモリシステムの最大転送速度はそれ. 1. —. 5,747. 1,558. ぞれ 12.8GB/sec と 51.2GB/sec で約 4 倍の向上であるか. 2. 648. 5,558. 2,415. ら，同じソースコードでの 2 倍から 3 倍程度の速度向上は. 4. 585. 5,415. 5,009. 妥当な範囲であろう．. 8. 936. 5,288. 7,864. で最大約 5 倍（AVX2 が使える演算の場合）の向上であり，. INVITR 再直交化無し. 表 1 のシステムで CPU の 1 コアだけを用いてランダムな要素を持つ対称帯行列のすべての固有対を求めた場合の経過時間の測定値の例を表 3 から表 8 に示す．表 3 経過時間（秒）：（次数 N =1, 000，半帯幅 h）. h. TRIDIA. BISECT. 表 8 経過時間（秒）：（次数 N =300, 000，半帯幅 h）. h. TRIDIA. BISECT. INVITR 再直交化有り. 1. —. 0.69. 0.11. 2. 0.066. 0.67. 0.16. 4. 0.058. 0.65. 0.24. 8. 0.068. 0.64. 0.42. INVITR 再直交化無し. 1. —. 49,357. 16,178. 2. 5,820. 47,593. 21,152. 4. 5,273. 46,241. 34,864. 4. いくつかの考察要素の値を区間 [−0.5, 0.5] の一様な乱数にした実験例か. 表 4 経過時間（秒）：（次数 N =3, 000，半帯幅 h）. h. TRIDIA. BISECT. INVITR 再直交化有り. 1. —. 5.95. 1.36. 2. 0.60. 5.80. 2.28. 4. 0.53. 5.64. 4.18. 5. 0.53. 5.56. 3.75. 8. 0.57. 5.49. 27.63. 10. 0.64. 5.45. 21.34. 20. 0.81. 5.40. 59.87. 40. 1.11. 5.40. 90.15. 80. 2.19. 5.42. 174.45. らは，行列の次数 N を一定にして半帯幅 h を増加させたとき，局在化した領域は拡がるが固有ベクトルの「分布の半径」r は h に比例するのではなくて h の約 3/2 乗に比例する傾向がみられた．今回はまだ確認していないが，半帯幅 h 一定で行列次数. N を十分に大きくすると，それは近接相互作用を持つ 1 次元的な系の離散化に相当するから，行列要素がランダム性を含むと固有ベクトルはみな局在化するはずである．（これは一見奇妙に思える．例えば 1 次元の等間隔格子上のラプラシアンの差分近似は対称 3 重対角行列を与えるが，それに対称でランダムな摂動を加えると，いくら摂動が弱くても格子点数を十分大きくすれば，固有ベクトルはすべて局在化して固有ベクトルは正弦波的ではなくなる．）次数 N を有限で止めると，局在化の起きる状況は行列要. 表 5 経過時間（秒）：（次数 N =10, 000，半帯幅 h）. h. TRIDIA. BISECT. 素に含まれるランダム性の強さにも依存するであろう．含. INVITR. まれるランダム性が強いほど局在化しやすいであろう．ま. 再直交化有り. た固有ベクトルに強く局在化しているものとそうでないも. 1. —. 63.0. 1,837. のが混ざるであろう．次数 N が十分大きくない，または. 2. 6.42. 61.2. 2,043. 行列要素に含まれるランダム性が弱いと固有ベクトルの. 4. 5.68. 59.4. 2,171. 「分布の半径」は N に対して小さくなくて局在化していな. 8. 6.61. 57.9. 2,312. いとされるかもしくは局在化が弱い／不完全であるとなる. ⓒ 2015 Information Processing Society of Japan. 23.

(24) Vol.2015-HPC-150 No.12 2015/8/4. 情報処理学会研究報告 IPSJ SIG Technical Report. のであろうか．「N の大きさ」，「半帯幅 h」，「行列要素の. き，固有ベクトルが局在化する現象が重要になる場合が増. ランダム性の強さ」，「局在長」の間の関係を解明すること. えるであろうと思われます．. が望ましい（あるいはこのことは既に解明がされているかもしれない）．. 参考文献 [1]. 4.1 固有値問題解法の性能評価への影響ランダム性を含む行列は固有値が互いに近接をしていな. [2]. い傾向があり，さらに固有ベクトルにも局在化の傾向がある．既存の固有値問題を解く算法の中には，固有値が近接していないと都合が良いものや固有ベクトルが局在化していると有利になるものがある．もしも固有値が近接していたり固有ベクトルが局在化していることで算法の計算量や. [3] [4]. 収束性や丸め誤差の近似解への影響が変わるのなら，ランダムな行列を例題として得られた性能の測定値（計算時間，. [5]. 反復回数，計算誤差など）は，ランダム性を持たない場合. [6]. の性能の予測や参考値としてはあまり適切ではない可能性がある．局在化しているベクトルは，大きさが微小な要素を零で. [7] [8]. 置き換えて近似したり，微小な大きさの要素は数値を表現する有効桁数を減らすなどにより記憶に必要な量が圧縮で. [9]. きる可能性や，計算を反復法などで行う場合には部分的に. [10]. 低精度で計算することで実質的な演算量が低減できる可能性もある．局在化しているベクトル同士の内積の計算は一般的なベ. [11] [12]. クトル同士の場合よりも得られる結果の精度が高くなるし，総和の中から相対的に微小で無視できる値を省くこと. [13]. で計算量も減らせる．近似対を逆反復法で求めて改良する場合に，固有値が近. [14]. 接している組に対して近似固有ベクトルの再直交化処理を. [15]. 加えることで精度を維持しようとする計算では，固有ベクトルが局在化していると，相互の局在化領域に重なりがなければ，最初からほとんど直交しているので直交化処理を. [16] [17]. 省けて有利になることがある．. 4.2 局在化された固有解の近似的解法局在化している固有ベクトルの近似値は少ない計算量で. [18] [19]. 求めることができる．局在化領域を含む領域の外部に対する添字を持つ要素の値をすべて零と置いて近似すれば，元の固有値問題に比べて小規模の固有値問題が得られる．小. [20]. MACHIDA, Manabu:“Note on Anderson Localization”, 資料”2003 年度宮下研夏の勉強会”, URL(http://hatanolab.iis.u-tokyo.ac.jp/machida/doc/localization 02.pdf) Junko Yamasaki:“A New algorithm of Analyzing the Anderson Localization”, (MASTER THESIS), URL(http://hatano-lab.iis.utokyo.ac.jp/guidance/thesis /shuron2001/thesis yamasaki.pdf) P.W. Anderson:“Absence of Diﬀusion in Certain Random Lattices”, Phys. Rev., 109 (1958), pp.1492–1505. 福山秀敏:「アンダーソン局在」, 物理学最前線 2, 共立出版 (1983). 川畑有郷:「アンダーソン局在のスケーリング理論」, 物理学最前線 13, 共立出版 (1985). 長岡洋介, 安藤恒也, 高山一:「局在・量子ホール効果・密度波」, 1 章 1 節–2 節, 現代の物理学 18, 岩波書店 (1993). 大槻東巳:「不規則電子系の金属-絶縁体転移」, 現代物理学最前線 2, 共立出版 (2000), pp.75–142. 小野嘉之:「金属絶縁体転移」, 5 章–6 章, 朝倉物性物理シリーズ 1, 朝倉書店 (2002). 川畑有郷:「固体物理学」, 6 章 4 節, [物理の考え方 3], 朝倉書店 (2007) 小谷眞一:「ランダム・ポテンシャルの問題」, 数学, 38, 岩波書店 (1986), pp.53–61. 氷上忍:「ランダム・ポテンシャルの問題に対する補足」, 数学, 38, 岩波書店 (1986), pp.61–65. 小谷眞一: (論説)「ランダム・ポテンシャルの問題 II」, 数学, 38, 岩波書店 (1986), pp.193–201. 第 14 回日本数学会彌永賞（小谷眞一）, 「ランダムなポテンシャルをもつ Schr¨ odinger 作用素のスペクトル理論」, 数学, 38, 岩波書店 (1986), p.265. 福島正俊:「ランダム Schr¨ odinger 作用素に関する小谷理論」, 数学, 38, 岩波書店 (1986), pp.266–269. 小沢真:「ランダム媒質のスペクトル」, 数学, 44, 岩波書店 (1992), pp.306–319. 永尾太郎「 : ランダム行列の基礎」, 東京大学出版会 (2005). Martin R.S. and Wilkinson J.H.: “Solution of symmetric and unsymmetric band equations and the calculations of eigenvectors of band matrices”, Numer. Math.,9 (1967), pp.279–301 . 村田健郎, 小国力, 唐木幸比古: 「スーパーコンピュータ科学技術計算への適用」, 丸善 (1985). 小国力編, 村田健郎, 三好俊郎, ドンガラ J.J., 長谷川秀彦共著: 「行列計算ソフトウェア - WS, スーパーコン, 並列計算機 - 」, 丸善 (1991). 村上弘:「固有値解析とアンダーソン局在」, 情報処理学会研究報告, 2007-HPC-112, No.7 (2007 年 9 月), pp.33–35.. 規模の固有値問題を解いて得られた固有ベクトルから最初に仮定した局在性を満たしているものを選択する．得られ x ) が元の固有値問題 Bx = λx の十分に良いた近似対 (λ, 近似対であるかを調べるには，元の方程式の残差ベクトル x を求めれば良いが，x の非零要素の添字の範囲 (B − λI) は狭いので行列ベクトル積は高速に計算できる．. 5. 終わりに今後，固有値問題の計算がますます大規模化していくと. ⓒ 2015 Information Processing Society of Japan. 24.

(25)