ふたつのnxn行列の普通の掛け算ではn^3回の乗算が必要になる。

1960年代に見いだされたシュトラッセン法は２次の行列同士の積に対して，８回のかけ算を７回ですませる方法であった．

　Ｎ＝２^nの場合，行列を２^n-1×２^n-1の４つのコンパートメントに分割して，それぞれに対してシュトラッセン法を適用することができる．このとき，

　　ｌｏｇ2（７）＝２．８０７３５

より，計算量は

　　Ｏ（Ｎ^3）→Ｏ（Ｎ^2.807・・・）

シュトラッセン法は大きなサイズの行列には有効な方法である。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ラダーマン法は３次の行列同士の積に対して，２７回のかけ算を２３回ですませる方法であった．

　Ｎ＝３^nの場合，ｌｏｇ3２３＝２．８５４０５より，計算量は

　　Ｏ（Ｎ^3）→Ｏ（Ｎ^2.85）

になる．

　　ｌｏｇ2７＜ｌｏｇ3２３

より，ラダーマン法はシュトラッセンの方法を改良したことにはなっていないのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1960年代に見いだされたシュトラッセン法には誰もが驚いたものである。一方、量子コンピュータは(2^n)x(2^n)行列の乗法を提供する。高速因数分解の問題を解くことができるため、現在広く使われている公開鍵暗号が破られることを意味している

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　フーリエ変換（ＦＴ）は，三角関数の性質を利用した積分変換解析法で，１９世紀初頭，鉄の輪を熱したときの温度分布を解析するなど熱伝導の考察から誕生し，波動や振動現象の解明をはじめ多くの応用分野をもっています．また，１９６５年に大量のデータを速度を重視して解析するテクニックとして開発されたのが，高速フーリエ変換（ＦＦＴ）です．ＦＦＴは今日ではコンピュータと結びついて画像処理などの技術に利用されています．

元の関数をフーリエ級数で表現するためにはFfの計算が必要になる。ここで、Fは行列でFij=exp(2πi/n・jk),fはｎ成分のベクトル。

n^2回の掛け算が必要になるが、クーリーとチューキーはnlogn回掛け算しか必要としないアルゴリズムを発見したのである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝