SVM CLassification for Predicting Sparse Matrix Solvability
with Parameterized Matrix Preconditioners

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

Abstract

Large sparse linear systems are routinely solved using preconditioned Krylov subspace methods, in which the suitability and quality of the preconditioners play the vital role in determining the convergence rate of the iteration scheme. Selecting a suitable preconditioner for a specific sparse matrix arising from a particular application presents a challenging task for many application scientists and engineers who have little knowledge of preconditioned iterative methods. In this paper, we propose to use data mining techniques to predict the solving status of general sparse matrices with incomplete LU factorization type preconditioners with parameters. This work follows our previous work to use data mining techniques to predict the solvability of general sparse matrices with parameter-free matrix structure-based incomplete LU type preconditioners. Our proposed method chooses some points in the parameter space as samples. Studying the performance of a typical preconditioner, e.g., ILUT, with these sample parameters, we can get the main idea of what kinds of combination of the parameters are favorable for a given sparse matrix. If we can correctly predict the solving status at these sample points, we may obtain an outline of the parameter area(s) in which the sparse matrix can be solved. We use support vector machine (SVM) classification to predict the solving status of the sparse linear systems by ILUT with a specific set of parameters. We also use singular value decomposition (SVD) and sparsified SVD to preprocess the matrix features to improve the accuracy of prediction. We focus our work on ILUT preconditioner, but the proposed strategies should be applicable to other preconditioners with parameters.


Key words: sparse matrix, support vector machine, preconditioning

Mathematics Subject Classification:


Download the compressed postscript file xu7.ps.gz, or the PDF file xu6.pdf.
Technical Report 450-06, Department of Computer Science, University of Kentucky, Lexington, KY, 2006.

The research work of J. Zhang was supported in part by NSF under grants CCR-0092532, ACR-0202934, and CCF-0527967, and in part by Kentucky Science and Engineering Foundation.