【行列累乗より速い😍】K項間線形漸化式のN項目を高速に求める~行列累乗の3乗の項にうんざりしたあなたにおすすめの最強線形代数活躍算法Fidduciaのアルゴリズムのご紹介です~
K+1項間の線型漸化式を持つ数列のN項目は行列累乗を使うと O(K^3 log N)の計算量で求めることができるということはよく知られています。しかし、このスライドで紹介するFiducciaのアルゴリズムを使うと、(FFTができたりする良い条件のもとで) O(K log K log N)で計算できます。 (FFTができないなどの理由で愚直な筆算をする場合はO(K^2 log N)になる)
Harui
January 11, 2025