行列とベクトルの乗算 (BLAS2) と行列と行列の乗算 (BLAS3) のパフォーマンスの最適化に関する多くの論文を読んできました。これらの最適化が、密または疎の線形代数にきれいに還元されない O(n^2) および O(n^3) アルゴリズムに適用されるかどうか、またはどのように適用されるかについて考えたいと思います。
NP 完全アルゴリズムまたは NP 困難アルゴリズムのリストを見つけるのは簡単ですが、一般的な (そしてそれほど一般的ではない) 多項式時間アルゴリズムの適切な内訳は見つかりませんでした。最もよく知られているアルゴリズムが O(n^2) または O(n^3) である多項式時間の問題のリストを提案できる人はいますか?
編集:これをより具体的にするために、このNP 完全問題のリストのようなものを探していますが、代わりに n^2 または n^3 アルゴリズムを使用した多項式の問題を探しています。
まず、レベル2およびレベル3のBLAS操作の複雑さは、実際には正式にはO（n）およびO（n ^ 3/2）であることに注意してください。入力行列は、人々が通常「n」と考えるものでは、それ自体が2次式です。
密な線形代数に一般的に使用される手法は、問題の線形性を多用する傾向があるため、他の問題領域に直接適用されることはありません。
次へ：O（n ^ 2）アルゴリズムの最も一般的な例のいくつかは、ソート、整数乗算、および離散フーリエ変換の計算のための単純なアルゴリズムです。これらすべての場合において、複雑度の低い、より優れたアルゴリズムが存在します。同様に、ナイーブなO（n ^ 3）アルゴリズムが多数あります。
DFTの計算に高密度線形代数手法を適用することもできますが（線形でもあるため）、FFTアルゴリズムの1つを使用することでさらに優れた結果が得られるため、実際には誰もこれを行いません。
ナイーブでないアルゴリズムに関する限り、複雑さのコースを教えなければならなかったので、それは長すぎました。文字列が文脈自由言語であるかどうかを判断するための最もよく知られているアルゴリズムであるIIRCはO（n ^ 3）です。