 Sparse Iterative Method Options - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Solvers : LinearAlgebra/General/LinearSolveItr

Sparse Iterative Method Options

 The LinearAlgebra[LinearSolve] function can be used to solve linear systems of the form $\mathrm{Ax}=b$ for the unknown x. When A is a sparse symmetric Matrix, an iterative solver may be chosen by specifying the method=SparseIterative option in the call to LinearSolve.  The methodoptions=list option may also be provided to LinearSolve to control the behavior of the iterative method.  The elements of this list may be one or more of the options listed below.  The variable n refers to the dimension of the linear system.
 *    itermethod=methodname, where methodname is either CG or SYMMLQ; iterative method
 *    precon=true or false; use a preconditioner if precon=true is specified
 *    levelfill=k, where k is of type nonnegint; level of fill
 *    droptol=d, where d is of type nonnegative; drop tolerance
 *    norm=p, where p is one of 1, 2, infinity, Euclidean; norm for stopping criterion
 *    matnorm=v where v is of type positive; matrix norm estimate
 *    toler=tval where tval is of type nonnegative; tolerance for stopping criterion
 *    maxiter=m where m is of type posint; maximum iterations
 *    modify=true or false; use a modified factorization if modify=true is specified
 *    diagscal=ds where ds is of type nonnegative; use diagonal scaling factor of 1.0+ds
 *    pivot=true or false; use pivoting if pivot=true is specified
 *    weight=w, where w is a Vector of n nonnegative values; weights for stopping criterion
 *    initsol=x0, where x0 is a Vector of n nonnegative values; initial solution values
 *    precstor=ps, where ps is of type posint; preconditioner workspace dimension
 These options are described in detail in the sections below. The options in the provided list are processed in the order in which they appear; thus, subsequent options may override earlier ones if they conflict.

General Options

 The itermethod option determines if the Conjugate Gradient (CG) method or the SYMMLQ method is used.  If this option is not specified and the matrix has the positive_definite attribute, then the CG method is used; otherwise the SYMMLQ method is used.  The CG method is designed for positive-definite matrices and may fail for indefinite matrices.  The SYMMLQ method is appropriate for both positive-definite and indefinite matrices, but is less efficient than the CG method with positive-definite matrices.
 The initsol option is used to provide an initial solution to the sparse solver.  Otherwise, the initial solution is the zero vector.

Preconditioning Options

 The precon option is used to specify whether preconditioning should be applied, and it is set to precon=true by default.  An incomplete Cholesky factorization with no additional fill is used as the preconditioner, unless a different type of preconditioner is specified.  The preconditioner must be symmetric positive-definite.
 The levelfill=k option is used to specify a preconditioner with level k fill.  Alternatively, the droptol option can be used to specify a drop tolerance to control the fill.  The droptol option is ignored if the levelfill option is provided.
 The modify option is used to specify that the factorization should be modified to preserve row sums.  The default is modify=false, i.e. an unmodified factorization.
 The diagscal=ds option is used to specify that the diagonal elements should be multiplied by a factor of 1.0+ds at the start of the factorization.  This can be used to ensure that the preconditioner is positive-definite.  The default is no scaling.
 The pivot option is used to specify whether a pivoting strategy is to be applied.  The default is pivot=true, which results in the Markowitz pivoting strategy to minimize fill-in.  If pivot=false is specified, then no pivoting takes place.
 The precstor=ps option is used to specify the dimension of the preconditioner workspace.  The dimension is set to the maximum of ps and a default value based on the problem size and type of preconditioner.

Stopping Criteria

 The stopping criterion used is $‖r‖\le t\left(‖b‖+‖A‖‖x‖\right)$ where r and x refer to the current residual and solution values at a particular iteration.  The default norm is the infinity norm. The norm=p option (with p set to 1, 2, Euclidean or infinity) is used to specify a different norm.
 The matnorm option is used to provide an estimate for $‖A‖$.  This estimate must be provided if the norm=2 or norm=Euclidean option is specified.  Otherwise, an estimate is automatically generated by the solver.
 The weight option is used to specify a Vector of weights to be used in computing the vector norms in the stopping criterion.  The default is no weighting.
 The toler=tval option is used to set the value of t in the stopping criterion.  The value t is calculated as $\mathrm{max}\left(\mathrm{tval},10\mathrm{eps},\sqrt{n}\mathrm{eps}\right)$ where eps is the machine precision.  If the toler option is not provided, a default value is used.
 The maxiter option is used to specify the maximum number of iterations performed.  If this is not provided, a default value is used.

 Details about the various settings and final statistics may be obtained through userinfo statements.  These can be displayed by setting the value of infolevel[LinearAlgebra].
 When an incomplete Cholesky factorization preconditioner is created with levelfill set to a value greater than 0 or with a drop tolerance specified, it is difficult to predict the amount of fill that will be produced.  The LinearSolve routine may issue an error message indicating that not enough preconditioner workspace was available.  This problem may be resolved by increasing the workspace with the precstor option, decreasing the level of fill, or increasing the drop tolerance.

Examples

 > with(LinearAlgebra):
 > M := Matrix(4,4,[[5.0],[0.2,-1.0],[0.0,3.0,0.0],[-2.0,0.0,0.0,1.0]],   shape=symmetric,storage=sparse[lower],datatype=float):
 > b := Vector(4,1.0,datatype=float):
 > LinearSolve(M,b,method=SparseIterative,methodoptions=[itermethod=CG,levelfill=1]);
 $\left[\begin{array}{c}{2.93333333333333}\\ {0.333333333333332}\\ {0.248888888888889}\\ {6.86666666666666}\end{array}\right]$ (1)