A robust parallel solver for block tridiagonal systems

ABSTRACT

An iterative method for the solution of nonsymmetric linear systems of equations is described and tested. The method, block symmetric successive over-relaxation with conjugate gradient acceleration (BSSOR), is remarkably robust and when applied to block tridiagonal systems allows parallelism in the computations. BSSOR compares favorably to unpreconditioned conjugate gradient-like algorithms in efficiency, and although generally slower than preconditioned methods it is far more reliable. The concept behind BSSOR can, in general, be applied to sparse linear systems (even if they are singular), sparse nonlinear systems of equations and least squares problems.

REFERENCES

• AnSaS8: Edward Anderson , Yousef Saad, Preconditioned Conjugate Gradient Methods for General Sparse Matrices on Shared Memory Machines, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.88-92, December 01-04, 1987
• BjEl79: A. Bjorck and T. Elfving, "Accelerated projection methods for computing pseudo-inverse solutions of systems of linear equations," B/T, vol. 19, pp. 145- 163, 1979.
• DBMS79: J. Dongarra, J. Bunch, C. Moler, and G. Stewart, Linpack User's Guide, SIAM, Philadelphia, 1079.
• EiES83: S. Ei~senstat, H. Elman, and M. Schultz, '~rariational iterative methods for nonsymmetric systems of linear equations", SIAM J. Numerical Analysis, vol. 20, pp. 345-357, 1983.
• Elma82: Howard C. Elman, Iterative methods for large, sparse, nonsymmetric systems of linear equations, 1982
• Elfv78: T. Elfving, "On the conjugate gradient method for Solving linear least squares problems", LiTH-MAT- R-1978-3, Department of Mathematics, Linkoplng University, S-58183 Linkoping Sweden, 1978.
• GoVL83: G. Golub and C. Van Loan, Matrix Computations, John Hopkins University Press, Baltimore, 1983.
• GoPS86: G. Golub, R. Plemmons and A. Sameh, '~araIlel block schemes for large scale least squares computations", CSRD Rept. 574, Center for Supercomputing Research and Development, University of Illinois, Urbana, IL, April 1986.
• Kacz37: S. Kaczmarz, "Angenaherte Auflosung yon Systemen linearer Gleichungen," Bull. Internat. Polos. Sci. Cl. .4, pp. 355-357, 1937.
• KaSa86: C. Kamath and A. Sameh, "A projection method for solving nonsymmetric linear systems on multiprocessors," CSRD Rept. 611, Center for Supercomputing Research and Development, University of Illinois, Urbana, IL, October 1986.
• PaSa82: Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982 [doi>10.1145/355984.355989]
• Reid71: J. Reid, "On the method of conjugate gradients for the solution of large sparse systems of linear equations," Large Sparse Sets of Linear Equation,, ed. J. Reid, Academic Press, pp. 231-254, 1971.
• SaSc86: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
      G.1.6 Optimization
          Subjects: Least squares methods

General Terms:
Algorithms, Design