The module cvxopt.umfpack includes four functions for solving sparse non-symmetric sets of linear equations. They call routines from the UMFPACK library, with all control options set to the default values described in the UMFPACK user guide.

See also:

• UMFPACK code, documentation, copyright and license.
• T. A. Davis, Algorithm 832: UMFPACK - an unsymmetric-pattern multifrontal method with a column pre-ordering strategy, ACM Transactions on Mathematical Software, 30(2), 196-199, 2004.

linsolve(A, B[, trans='N'])

Solves a sparse set of linear equations

where A is a sparse matrix and B is a dense matrix of the same type ('d' or 'z') as A. On exit B contains the solution. Raises an ArithmeticError exception if the coefficient matrix is singular.

In the following example we solve an equation with coefficient matrix

>>> from cvxopt.base import spmatrix, matrix
>>> from cvxopt import umfpack 
>>> V = [2,3, 3,-1,4, 4,-3,1,2, 2, 6,1]
>>> I = [0,1, 0, 2,4, 1, 2,3,4, 2, 1,4]
>>> J = [0,0, 1, 1,1, 2, 2,2,2, 3, 4,4]
>>> A = spmatrix(V,I,J)
>>> B = matrix(1.0, (5,1))
>>> umfpack.linsolve(A,B)
>>> print B
[ 5.79e-01]
[-5.26e-02]
[ 1.00e+00]
[ 1.97e+00]
[-7.89e-01]

The function umfpack.linsolve() is equivalent to the following three functions called in sequence.

symbolic(A)

Reorders the columns of A to reduce fill-in and performs a symbolic LU factorization. A is a sparse, possibly rectangular, matrix. Returns the symbolic factorization as an opaque C object that can be passed on to umfpack.numeric().

numeric(A, F)

Performs a numeric LU factorization of a sparse, possibly rectangular, matrix A. The argument F is the symbolic factorization computed by umfpack.symbolic() applied to the matrix A, or another sparse matrix with the same sparsity pattern, dimensions, and type. The numeric factorization is returned as an opaque C object that that can be passed on to umfpack.solve(). Raises an ArithmeticError if the matrix is singular.

solve(A, F, B[, trans='N'])

Solves a set of linear equations

where A is a sparse matrix and B is a dense matrix of the same type as A. The argument F is a numeric factorization computed by umfpack.numeric(). On exit B is overwritten by the solution.

These separate functions are useful for solving several sets of linear equations with the same coefficient matrix and different righthand sides, or with coefficient matrices that share the same sparsity pattern. The symbolic factorization depends only on the sparsity pattern of the matrix, and not on the numerical values of the nonzero coefficients. The numerical factorization on the other hand depends on the sparsity pattern of the matrix and on its the numerical values.

As an example, suppose A is the matrix (7.1) and

which differs from A in its first and last entries. The following code computes

>>> from cvxopt.base import spmatrix, matrix
>>> from cvxopt import umfpack
>>> VA = [2,3, 3,-1,4, 4,-3,1,2, 2, 6,1]
>>> VB = [4,3, 3,-1,4, 4,-3,1,2, 2, 6,2]
>>> I =  [0,1, 0, 2,4, 1, 2,3,4, 2, 1,4]
>>> J =  [0,0, 1, 1,1, 2, 2,2,2, 3, 4,4]
>>> A = spmatrix(VA, I, J)
>>> B = spmatrix(VB, I, J)
>>> x = matrix(1.0, (5,1))
>>> Fs = umfpack.symbolic(A)
>>> FA = umfpack.numeric(A, Fs)
>>> FB = umfpack.numeric(B, Fs)
>>> umfpack.solve(A, FA, x)
>>> umfpack.solve(B, FB, x)
>>> umfpack.solve(A, FA, x, trans='T')
>>> print x
[ 5.81e-01]
[-2.37e-01]
[ 1.63e+00]
[ 8.07e+00]
[-1.31e-01]