Here, some of the most common calculations are summarized (in common sense):
Matrix multiplied:
§ Most original method: 2 * n ^ 3 n ^ 2 = o (n ^ 3)
§ STRASSEN algorithm: o (n ^ (log2 ^ 7))
§ Winograd & Coppersmith: o (n ^ 2.37)
Matrix vector multiplied:
§ Original method: o (n ^ 2)
Matrix Equation Solution:
§ Gaussine removed: o (n ^ 3) [forward iteration: o (n ^ 3), reverse iteration: o (n ^ 2)]
§ Complete matrix LU decomposition: o (n ^ 2) [forward iteration: o (n ^ 2), reverse iteration: o (n ^ 2)]
§ Belt matrix LU decomposition: o (m * n) (m is bandwidth)
§ three diagonal LU decomposition: o (n)
Torque inversion:
§ Multiplore the matrix (three results)
Finite element:
§ Two-dimensional finite element LU decomposition: o (n ^ (3/2)))
§ 3D finite element LU decomposition: o (n ^ 2)
§ Second, three-dimensional finite element iterative algorithm (CG / BCG): o (n)
Time domain limited difference:
§ 2D FDTD (determined time t): o (n ^ (3/2))
§ 3D FDTD (determination time t): o (n ^ (4/3))
Sort:
§ Quicksort: O (N * log (n))
§ BucketSort: o (n) (best case)
FFT: O (N * log (n)) Fast Multiode FMM: O (N * log (n))
Most binary-based algorithms can be optimized to O (N * log (n))
[Waiting to be added]
Reference: GH Golub / Van Loan "Matrix Computations", 1989PC Hansen "Rank-Deficient and Discreate Ill-Posed Problems", 1998WC CHEW "Waves and Fields in inhomogeneous Media", 1990
Thanks to KimbTsing@yahoo.com.cn, it is found that the computational complexity of FMM in Computational CPX is wrong. It should be o (n ^ 1.5), and MLFMA (multi-layer fast multipole) is O (Nlog) N)) Document see the original follow-up.
