Sparse iterative methods

H. A. V. der Vorst, T. F. Chan. Linear System Solvers Sparse Iterative Methods (in Parallel Numerical Algorithms). Volume 4 of ICASE/LaRC Interdisc. Ser. in Science and Engineering, p. 167-202, Dordrecht, 1997. Kluwer Academic. 

Sparse matrices are ones in which the majority of the elements are zero. If the structure of the matrix is exploited, the solution time on a computer is greatly reduced. See Duff, I. S., J. K. Reid, and A. M. Erisman (eds.), Direct Methods for Sparse Matrices, Clarendon Press, Oxford (1986) Saad, Y., Iterative Methods for Sparse Linear Systems, 2d ed., Society for Industrial and Applied Mathematics, Philadelphia (2003). The conjugate gradient method is one method for solving sparse matrix problems, since it only involves multiplication of a matrix times a vector. Thus the sparseness of the matrix is easy to exploit. The conjugate gradient method is an iterative method that converges for sure in n iterations where the matrix is an n x n matrix. 

Saad, Y. Iterative Methods for Sparse Linear Systems Available online http //www-users.cs.umn.edu/ saad/books.html, 2000. 

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edn, Society for Industrial and Applied Mathematics (2003). 

There are four methods for solving systems of linear equations. Cramer s rule and computing the inverse matrix of A are inefficient and produce inaccurate solutions. These methods must be absolutely avoided. Direct methods are convenient for stored matrices, i.e. matrices having only a few zero elements, whereas iterative methods generally work better for sparse matrices, i.e. matrices having only a few non-zero elements (e.g. band matrices). Special procedures are used to store and fetch sparse matrices, in order to save memory allocations and computer time. 

We see that because of the structure of the equations the coefficient matrix is very sparse. For this reason iterative methods of solution may be very efficient. 

T. C. Oppe, W. D. Joubert, and D. R. Kincaid, NSPCG User s Guide. Version 1.0 A Package for Solving Large Sparse Linear Systems by Various Iterative Methods. Technical Report CNA-216, Center for Numerical Analysis, University of Texas at Austin, 1988. 

The matrices derived from partial differential equations are always sparse, i.e. most of their elements are zero. For one-dimensional systems the discretization process leads to tri-diagonal systems, a system with only three non-zero coefficients per equation. Since the systems are often very large we find that iterative methods are generally much more economical than direct methods. 

In cases where iterative methods are employed to solve large, sparse linear systems, both the efficiency and robustness of these methods can be significantly improved by use of preconditioners. A preconditioner of a matrix A is a matrix such that has a smaller condition number than A. The... 

Y. Saad. Iterative methods for sparse linear systems. SIAM, 2003. 

There are a number of methods available to solve for the solution of a given set of linear algebraic equations. One class is the direct method (i.e., requires no iteration) and the other is the iterative method, which requires iteration as the name indicates. For the second class of method, an initial guess must be provided. We will first discuss the direct methods in Section B.5 and the iterative methods will be dealt with in Section B.6. The iterative methods are preferable when the number of equations to be solved is large, the coefficient matrix is sparse and the matrix is diagonally dominant (Eqs. B.8 and B.9). 

When dealing with large sets of equations, especially if the coefficient matrix is sparse, the iterative methods provide an attractive option in getting the solution. In the iterative methods, an initial solution vector is assumed, and the process is iterated to reduce the error between the iterated solution and the exact solution x, where k is the iteration number. Since the exact solution is not known, the iteration process is stopped by using the difference Ax, = -... 

Iterative algorithms are recommended for some linear systems Ax = b as an alternative to direct algorithms. An iteration usually amounts to one or two multiplications of the matrix A by a vector and to a few linear operations with vectors. If A is sparse, small storage space suffices. This is a major advantage of iterative methods where the direct methods have large fill-in. Furthermore, with appropriate data structures, arithmetic operations are actually performed only where both operands are nonzeros then, D A) or 2D A) flops per iteration and D(A) + 2n units of storage space suffice, where D(A) denotes the number of nonzeros in A. Finally, iterative methods allow implicit symmetrization, when the iteration applies to the symmetrized system A Ax = A b without explicit evaluation of A A, which would have replaced A by less sparse matrix A A. 

Error Reduction in Classic Iterative Methods. Iterative methods for the solution of large sparse systems of equations have been presented here. These methods produce, by iteration, a sequence of approximations to the required solution, which converge to the solution. This process progressively reduces the error related to each approximation. A given approximation is then accepted as the solution when the deviation from the previous approximation (or some norm of it) is smaller than a predefined threshold. Therefore, an analysis of the error expressed in Eq. [30] as a function of the iteration number (or of the required computer time, because the number of operations per iteration is constant) can provide a useful indication of the solver performance. 

In this paper, we studied the problems of parametric dictionary (PD) design for sparse representations. We can see that by minimizing the distance between C norm of column of designed dictionary and Gram matrix, the resultant dictionary will have the minimum mutual coherence compared to initial dictionary. By the mean of constant characteristic of gram matrix, we eliminate the iteration method that was used in previous methods, enabling better results. 

---