A Data Mining Approach to Matrix Preconditioning Problem

Shuting Xu, and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA


Preconditioned Krylov subspace methods are generally used to solve large sparse linear systems with sparse coefficient matrices. However, choosing an efficient preconditioner for a specific sparse matrix arising from a particular application presents a formidable challenge for many design engineers and application scientists who have little knowledge of preconditioned iterative methods. We propose to build an Online Preconditioner Prediction System, which can predict the solvability of general sparse matrices with structure-based sparse matrix preconditioners using data mining techniques. We first group matrices into clusters, then use Support Vector Machine Classification technique to predict the solving status of the sparse matrices in clusters with low purity values. The prediction method can predict whether a matrix can be solved by a preconditioner (in a preconditioned iterative solver). In the case of a negative prediction, the method can also predict the possible reasons why the matrix cannot be solved by this preconditioner. Our experimental results show that the overall accuracy of the prediction is above 90% for the ILU0 preconditioner and above 87\% for the ILUK preconditioners.

Key words: Sparse matrices, support vector machine, preconditioning

Mathematics Subject Classification:

Download the compressed postscript file xu5.ps.gz, or the PDF file xu5.pdf.
Technical Report 433-05, Department of Computer Science, University of Kentucky, Lexington, KY, 2005.

The research work of S. Xu was supported in part by the U.S. National Science Foundation under grant ACR-0234270.

The research work of J. Zhang was supported in part by NSF under grants CCR-0092532 and ACR-0202934, by DOE under grant DE-FG02-02ER45961, and by the University of Kentucky Research Committee.