LSSP

From HandWiki

LSSP is a Linear Solver library for SParse linear system, Ax = b. The package is designed for Linux, Unix and Mac systems. It is also possible to compile under Windows OS. The code is serial.

LSSP has many built-in solvers and preconditioners, and it also has interfaces to external packages, such as PETSc, MUMPS, FASP, UMFPACK (SUITESPARSE), KLU (SUITESPARSE), LASPACK, ITSOL, LIS, QR_MUMPS, PARDISO, SUPERLU, and HSL_MI20.

Internal solvers

GMRES, LGMRES, BICGSTAB, BICGSTABL, BICGSAFE, CG, CGS, GPBICG, CR, CRS, BICRSTAB, BICRSAFE, GPBICR, QMRCGSTAB, TFQMR, ORTHOMIN, and IDRS

External solvers

LASPACK, UMFPACK, KLU, MUMPS, PETSC, LIS, QR_MUMPS, FASP, AMG, SUPERLU, PARDISO, and HSL MI20AMG.

PETSC, LIS, and FASP are solver packages, which include many solvers and preconditioners. For example, FASP implements CG, BiCGstab, MinRes, GMRES, VGMRES, VFGMRES, GCG, GCR, SCG, SBiCGstab, SMinRes, SGMRES, SVGMRES, SVFGMRES, SGCG, AMG, and FMG.

Internal preconditioners

Incomplete LU factorization: ILUK, ILUT, and Block-wise ILUK.

External preconditioners

BILUT, VBILUT, VBILUK, ARMS, AMG and FMG (FASP), and MI20AMG (HSL).

Krylov solvers

GMRES

In mathematics, the generalized minimal residual method (usually abbreviated GMRES [1]) is an iterative method for the numerical solution of a nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The Arnoldi iteration is used to find this vector.

LGMRES

Augments the standard GMRES approximation space with approximations to the error from previous restart cycles.[2]

BICGSTAB

The biconjugate gradient stabilized method, often abbreviated as BiCGSTAB,[3] is an iterative method developed by H. A. van der Vorst for the numerical solution of nonsymmetric linear systems. It is a variant of the biconjugate gradient method (BiCG) and has faster and smoother convergence than the original BiCG as well as other variants such as the conjugate gradient squared method (CGS).

BICGSTABL

Biconjugate gradients stabilized (l) method.[4]

BICGSAFE

BICGSAFE was developed by Fujino et al.[5]

CG

The conjugate gradient method [6] is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems.

CGS

Conjugate gradients squared method (CGS).[7]

GPBICG

Generalized Product Bi-Conjugate Gradient (GPBiCG).[8]

CR

The conjugate residual method [9] is an iterative numeric method used for solving systems of linear equations. It's a Krylov subspace method very similar to the much more popular conjugate gradient method, with similar construction and convergence properties. This method is used to solve linear equations of the form, A x = b, where A is an invertible and Hermitian matrix, and b is nonzero. The conjugate residual method differs from the closely related conjugate gradient method primarily in that it involves more numerical operations and requires more storage, but the system matrix is only required to be Hermitian, not symmetric positive definite.

CRS

Conjugate Residual Squared method.[10]

BICRSTAB

Stabilized biconjugate residual method.

BICRSAFE

BICRSAFE was developed by Fujino et al.[11]

GPBICR

Generalized product-type bi-conjugate residual method.[12]

QMRCGSTAB

QMRCGSTAB was designed by Chan et al.[13]

TFQMR

Transpose-Free QMR.[14]

ORTHOMIN

ORTHOMIN was originally developed for reservoir simulation.[15]

IDRS

Induced Dimension Reduction method.[16]

Multigrid method

Multigrid method in numerical analysis is a method for solving differential equations using a hierarchy of discretizations.

References

  1. Y. Saad and M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7:856-869, 1986.
  2. A. H. Baker, E.R. Jessup, and T.A. Manteuffel. A technique for accelerating the convergence of restarted GMRES. SIAM Journal on Matrix Analysis and Applications, 26 (2005)
  3. H. Van der Vorst, Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems. SIAM J. Sci. and Stat. Comput., 1992, 13(2): 631–644
  4. GERARD L.G. SLEIJPEN AND DIEDERIK R. FOKKEMA, BICGSTAB(L) FOR LINEAR EQUATIONS INVOLVING UNSYMMETRIC MATRICES WITH COMPLEX SPECTRUM, Electronic Transactions on Numerical Analysis, 1993, Volume 1, pp. 11-32
  5. Seiji FUJINO, Maki FUJIWARA, Masahiro YOSHIDA, BiCGSafe method based on minimization of associate residual, Transactions of the Japan Society for Computational Engineering and Science Vol. 2005 (2005)
  6. Reference: Magnus Hestenes; Eduard Stiefel (1952). Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards. 49 (6)
  7. Peter Sonneveld, CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems, SIAM J. Sci. and Stat. Comput., 10(1), 36–52
  8. S.-L. Zhang, GPBi-CG: Generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 18 (1997), pp. 537–551
  9. Yousef Saad, Iterative methods for sparse linear systems (2nd ed.), SIAM.
  10. L. Zhang, X. Zuo, T. Gu, J. Xue, Conjugate residual squared method and its improvement for non-symmetric linear systems, International Journal of Computer Mathematics 87(7):1578-1590, 2010.
  11. S. Fujino, Y. Onoue, Estimation of BiCRSafe method based on residual of BiCR method (in Japanese). Technical Report 2007-HPC-111, IPSJ (2007)
  12. Kuniyoshi A, Sogabe T, Fujino S L, Zhang S L. A product-type Krylov subspace method based on conjugate residual method for nonsymmetric coefficient matrices [J]. IPSJ Trans Adv Comput Sys, 2007, 48(SIG8): 11-21
  13. Chan, T.F. and Gallopoulos, E. and Simoncini, V. and Szeto, T. and Tong, C.H., QMRCGSTAB: a Quasi-minimal Residual Variant of the Bi-CGSTAB Algorithm for Nonsymmetric Systems, University of Illinois at Urbana-Champaign, Center for Supercomputing Research and Development, 1992
  14. W. Freund (1993). A Transpose-Free Quasi-Minimal Residual algorithm for non-Hermitian linear systems. SIAM Journal on Scientific Computing 14.
  15. Orthomin, an Iterative Method for Solving Sparse Sets of Simultaneous Linear Equations, SPE-5729-MS, SPE Symposium on Numerical Simulation of Reservoir Performance, 19–20 February, Los Angeles, California, 1976
  16. Peter Sonneveld and Martin B. van Gijzen, IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems. SIAM J. Sci. Comput. Vol. 31, No. 2, pp. 1035-1062, 2008 (copyright SIAM).

External links