代数学コロキウム

過去の記録 ~03/27次回の予定今後の予定 03/28~

開催情報 水曜日 17:00~18:00 数理科学研究科棟(駒場) 117号室
担当者 今井 直毅,ケリー シェーン

2010年11月17日(水)

16:30-17:30   数理科学研究科棟(駒場) 056号室
原瀬 晋 氏 (東京大学大学院数理科学研究科)
F_2-線形擬似乱数発生法の評価に用いる格子の簡約基底計算の高速化 (JAPANESE)
[ 講演概要 ]
(部分的に松本眞氏、斎藤睦夫氏との共同研究)
擬似乱数発生法とは、あたかも乱数であるかのようにふるまう数列を、計算機上で
決定的なアルゴリズムにより発生する方法のことである。擬似乱数を評価する規準
の一つとして、高次元均等分布性がしばしば用いられる。メルセンヌツイスター法
を含む二元体上の線形擬似乱数発生法に対しては、上位ビットの均等分布の次元を
具体的に計算することが可能であり、擬似乱数の出力列から構成したある格子の簡
約基底を求める問題(二元体係数形式的冪級数体の数の幾何)に帰着される(Couture-
L'Ecuyer-Tezuka(1993)およびTezuka(1994))。本研究では、前述の格子を用いた
計算法を発展させ、
(i) 冪級数成分の格子点を擬似乱数発生器の状態ベクトルで表現する、
(ii) 射影を用いてv次元簡約基底からv-1次元簡約基底を計算する、
(iii) 効率的な格子簡約アルゴリズムを適用する、
などの手法を導入し、均等分布の次元計算の高速化を提案する。この方法は、
Couture-L'Ecuyer(2000)による双対格子を用いた改良よりも計算量が少なく、計算機
実験でも10倍程度の高速化が得られたことを紹介する。この結果は、ワードサイズの
大きな擬似乱数発生法の設計や擬似乱数の並列発生スキームなどへの応用が考えられる。