Linear Equations

 

We use the standard notation for a system of simultaneous linear equations:

 

where A is the coefficient matrix, b is the right hand side, and x is the solution. In (1) A is assumed to be a square matrix of order n, but some of the individual routines allow A to be rectangular. If there are several right hand sides, we write

 

where the columns of B are the individual right hand sides, and the columns of X are the corresponding solutions. The basic task is to compute X, given A and B.

If A is upper or lower triangular, (1) can be solved by a straightforward process of backward or forward substitution. Otherwise, the solution is obtained after first factorizing A as a product of triangular matrices (and possibly also a diagonal matrix or permutation matrix).

The form of the factorization depends on the properties of the matrix A. ScaLAPACK provides routines for the following types of matrices, based on the stated factorizations:

• general matrices (LU factorization with partial pivoting):

  

  where P is a permutation matrix, L is lower triangular with unit diagonal elements (lower trapezoidal if m > n), and U is upper triangular (upper trapezoidal if m < n).

• general band matrices including tridiagonal matrices
  • (LU factorization with partial pivoting): If A is m-by-n with kl subdiagonals and ku superdiagonals, the factorization is

    

    where L is a product of permutation and unit lower triangular matrices with kl subdiagonals, and U is upper triangular with kl+ku superdiagonals.

  • (LU factorization without pivoting) for matrices where it is known a priori that pivoting is not necessary for numerical stability, such as diagonally dominant matrices.
• symmetric and Hermitian positive definite matrices including band matrices (Cholesky factorization):

  

  

  where U is an upper triangular matrix and L is lower triangular.

• symmetric and Hermitian positive definite tridiagonal matrices ( factorization):

  

  

  where U is a unit upper bidiagonal matrix, L is unit lower bidiagonal, and D is diagonal.

The factorization for a general tridiagonal matrix is like that for a general band matrix with kl = 1 and ku = 1. The factorization for a symmetric positive definite band matrix with k superdiagonals (or subdiagonals) has the same form as for a symmetric positive definite matrix, but the factor U (or L) is a band matrix with k superdiagonals (subdiagonals). Band matrices use the band storage scheme described in section 3.2.

While the primary use of a matrix factorization is to solve a system of equations, other related tasks are provided as well.