Comparison of different numerical methods used to solve the Poisson equation. A bit old but still good.
Algorithm Type Serial PRAM Storage #Procs Time Time --------- ---- ------ --------- -------- ------ Dense LU D N^3 N N^2 N^2 Band LU D N^2 N N^(3/2) N Inv(P)*bhat D N^2 log N N^2 N^2 Jacobi I N^2 N N N Sparse LU D N^(3/2) N^(1/2) N*log N N CG I N^(3/2) N^(1/2)*log N N N SOR I N^(3/2) N^(1/2) N N FFT D N*log N log N N N Multigrid I N (log N)^2 N N Lower Bound N log N N Key to abbreviations: Dense LU : Gaussian elimination, treating P as dense Band LU : Gaussian elimination, treating P as zero outside a band of half-width n-1 near diagonal Sparse LU : Gaussian elimination, exploiting entire zero-structure of P Inv(P)*bhat : precompute and store inverse of P, multiply it by right-hand-side bhat CG : Conjugate Gradient method SOR : Successive Overrelaxation FFT : Fast Fourier Transform based method
Source: https://people.eecs.berkeley.edu/~demmel/cs267/lecture24/lecture24.html
1 comment:
All comments are welcome.
Post a Comment