IMSL_SP_PDFAC

The IMSL_SP_PDSOL function computes a factorization of a sparse symmetric positive definite system of linear equations Ax = b.

This routine requires an IDL Advanced Math and Stats license. For more information, contact your sales or technical support representative.

The IMSL_SP_PDFAC function computes a factorization of a sparse symmetric positive definite coefficient matrix A. In this function’s default usage, a symbolic factorization of a permutation of the coefficient matrix is computed first. Then a numerical factorization is performed.

The symbolic factorization step of the computation consists of determining a minimum degree ordering and then setting up a sparse data structure for the Cholesky factor, L. This step only requires the “pattern” of the sparse coefficient matrix, that is, the locations of the non-zero elements but not any of the elements themselves.

The numerical factorization can be carried out in one of two ways. By default, the standard factorization is performed based on a sparse compressed storage scheme. This is fully described in George and Liu (1981). Optionally, a multifrontal technique can be used. The multifrontal method requires more storage but will be faster in certain cases. The multifrontal factorization is based on the routines in Liu (1987). For a detailed description of this method, see Liu (1990), also Duff and Reid (1983, 1984), Ashcraft (1987), Ashcraft, et al. (1987), and Liu (1986, 1989).

If an application requires that several linear systems be solved where the coefficient matrix is the same but the right-hand sides change, IMSL_SP_PDFAC can be used to precompute the Cholesky factor. Then the keyword Factor can be used in IMSL_SP_PDSOL to efficiently solve all subsequent systems.

Given numeric factorization, x is obtained by the following calculations:

Ly₁ = Pb

L^Ty₂ = y₁

x = P^Ty₂

The permutation information, P, is carried in the numeric factor structure.

Example

A = REPLICATE(imsl_f_sp_elem, 10)

a(*).row = [0, 1, 2, 2, 3, 3, 4, 4, 4, 4]

a(*).col = [0, 1, 0, 2, 2, 3, 0, 1, 3, 4]

a(*).val = [10, 20, 1, 30, 4, 40, 2, 3, 5, 50]

b1 = [55, 83, 103, 97, 82]

b2 = [23, 55, 107, 197, 278]

factor = IMSL_SP_PDFAC(a, 5)

x1 = IMSL_SP_PDSOL(b1, FACTOR = factor)

PM, x1

  5.0000000

  4.0000000

  3.0000000

  2.0000000

  1.0000000

x2 = IMSL_SP_PDSOL(b2, FACTOR = factor)

PM, x2

  1.0000000

  2.0000000

  3.0000000

  4.0000000

  5.0000000

Syntax

Result = IMSL_SP_PDFAC([A], N_rows [, /CSC_COL] [, /CSC_ROW] [, /CSC_VAL] [, LG_DIAG=value] [, MULTIFRONTAL=value] [, N_NONZERO=variable] [, SM_DIAG=value])

Return Value

A one-dimensional array containing the solution of the linear system Ax = b.

Arguments

A

Sparse matrix stored as an array of structures containing non-zeros in lower triangle of the coefficient matrix A(i,j). See “Sparse Matrices: Direct Methods” and its related sections for a description of structures used for sparse matrices.

N_rows

The number of rows in a.

Keywords

CSC_COL (optional)

Accept the coefficient matrix in compressed sparse column (CSC) format. See “Sparse Coordinate Storage Format” for a discussion of this storage scheme. The keywords CSC_COL, CSC_ROW, and CSC_VAL must be used together.

CSC_ROW (optional)

CSC_VAL (optional)

LG_DIAG (optional)

The largest diagonal element that occurred during the numeric factorization.

MULTIFRONTAL (optional)

If present and nonzero, perform the numeric factorization using a multifrontal technique. By default a standard factorization is computed based on a sparse compressed storage scheme.

N_NONZERO (optional)

Named variable into which the total number of non-zeros in the factor is stored.

SM_DIAG (optional)

The smallest diagonal element that occurred during the numeric factorization.

Version History

6.4	Introduced

Module	Math&Stats

Version	9.0