The relationship between the features of sparse matrix and the matrix solving status

ABSTRACT

Solving very large sparse linear systems are often encountered in many scientific and engineering applications. Generally there are two classes of methods available to solve the sparse linear systems. The first class is the direct solution methods, represented by the Gauss elimination method. The second class is the iterative solution methods, of which the preconditioned Krylov subspace methods are considered to be the most effective ones currently available in this field. The sparsity structure and the numerical value distribution which are considered as features of the sparse matrices may have important effect on the iterative solution of linear systems. We first extract the matrix features, and then preconditioned iterative methods are used to the linear system. Our experiments show that a few features that may affect, positively or negatively, the solving status of a sparse matrix with the level-based preconditioners.

REFERENCES

• 1: G. H. Golub, H. A. van der Vorst. Closer to the solution: iterative linear solvers. In I. S. Duff and G. A. Watson, editors, The State of the Art in Numerical Analysis, pp. 63--92, Oxford, 1997.
• 2: Anne Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 3: N. Kang, J. Zhang, and E. S. Carlson. Parallel simulation of anisotropic diffusion with human brain DT-MRI data. Computers and Structures, Vol. 82, pp. 2389--2399 (2004)
• 4: George Karypis , Vipin Kumar, Parallel threshold-based ILU factorization, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-24, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509621]
• 5: J. Lee, J. Zhang, and C.-C. Lu. Performance of preconditioned Krylov iterative methods for solving hybrid integral equations in electromagnetics. J. of Applied Comput. Electromagnetics Society, Vol. 18, pp. 54--61 (2003)
• 6: http://math.nist.gov/MatrixMarket/
• 7: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 8: http://www-users.cs.umn.edu/saad/software/SPARSKIT/sparskit.html
• 9: S. Xu, J. Zhang. A new data mining approach to predicting matrix condition numbers. Communications in Information and Systems, Vol. 4, pp. 325--340 (2004).
• 10: S. Xu, J. Zhang. A data mining approach to matrix preconditioning problem. In Proceedings of the Eighth Workshop on Mining Scientific and Engineering Datasets (MSD'05), pp. 49--57 (2005)
• 11: Yin Wang , Jeonghwa Lee , Jun Zhang, A short survey on preconditioning techniques for large-scale dense complex linear systems in electromagnetics, International Journal of Computer Mathematics, v.84 n.8, p.1211-1223, August 2007 [doi>10.1080/00207160701355938]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms

Keywords:
ACM proceedings, features of matrices, iterative methods, preconditioner