松岡　栄光
2014/4/16 (水), 15:00-18:00
東京大学 工学部6号館 235号室

　一般の行列において対角化が重要な意味を持つのと同様に, 整数行列においては単因子標準形と呼ばれる標準形が重要な意味を持つ. 単因子標準形を求める高速なアルゴリズムの研究はこれまでもなされており, 中でも高速行列乗算を用いたアルゴリズムが理論上高速なものとして知られている([1], [2]). しかし, 高速行列乗算は漸近的に高速なアルゴリズムであり, 実用上で理論通りの性能が発揮されないものもある.
　本研究では, 高速行列乗算を用いた単因子標準形を求めるアルゴリズムの, 計算量の理論値と実際の計算時間との間にどの程度差があるのか, 計算機実験を行った. 十分な大きさを持つ密行列に対しては理論値に近い結果が得られたが, 特に疎行列に対しては必ずしも高速行列乗算を用いても速くなるわけではないことが分かった.

参考文献
[1]Wayne Eberly, Mark Giesbrecht, and Gilles Villard. On computing the determinant and Smith form of an integer matrix. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 675-685. IEEE, 2000.
[2]Arne Storjohann. Near optimal algorithms for computing Smith normal forms of integer matrices. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 267-274. ACM, 1996.