計算機数学I (2019) 第12回：行列積の法計算

今回は「モジュラー算法」と呼ばれる一連のアルゴリズムについて紹介しました。これは、多倍長整数でコストがかかる計算を、複数のより小さな整数を法とする剰余環に分けて計算し、複数の計算結果を中国剰余定理で合わせて整数上の計算結果を復元する方法です。

今回は、モジュラー算法の中から、行列積の計算を取り上げ、中国剰余算法を用いたアルゴリズムと、その計算量の見積もりを行いました。

次回は、今回の計算で出てきた、除算の計算量の見積もりと、中国剰余算法の計算量の見積もりを行います。