Cost Effective Machine Learning Approaches for Linear Solver Selection

Open Access
- Author:
- Toth, Brice Alan
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- June 05, 2009
- Committee Members:
- Padma Raghavan, Thesis Advisor/Co-Advisor
Padma Raghavan, Thesis Advisor/Co-Advisor - Keywords:
- machine learning
linear solvers
sparse matrices
cost reduction - Abstract:
- Numerical simulations are important in many areas of science and engineering. These simulations often involve the solution of large, sparse systems of linear equations. The solution time of these large, sparse linear systems dominates the execution time of the simulation. The choice of the linear system solution methods, in association with the characteristics of a given problem, directly influence the execution time. Selecting an effective solution method to match problem parameters is a key factor in reducing execution time and improving the performance and accuracy of the solution. The vast number of solution methods and the variability of the performance of solvers based on characteristics of a given problem make it difficult to determine the optimal method. Recent investigation in this domain have used machine learning techniques to choose an optimal solver. However, the computation of problem characteristics required by the learning algorithms are often time and memory intensive. For example, calculating problem characteristics, such as eigenvalues, can cause those techniques to take as long or more than running the solver. In this thesis, we present a method which utilizes low cost machine learning classifiers to select a solver for a given sparse system. We present a method for reducing the feature space of model characteristics, henceforth features. We use machine learning algorithms to produce classifiers and then compare their predictive accuracy and time for construction. We observe that these classifiers are less computationally expensive than the solver computation time. We show that reducing our large set of features to a smaller, cost-effective set saves computation time and can still be used to train machine learning algorithms to predict solvability of a given linear system within the same range of accuracy.