Year of Publication

2005

Degree Name

Doctor of Philosophy (PhD)

Document Type

Dissertation

College

Engineering

Department

Computer Science

First Advisor

Dr. Jun Zhang

Abstract

There are many scientific applications in which there is a need to solve very large linear systems. The preconditioned Krylove subspace methods are considered the preferred methods in this field. The preconditioners employed in the preconditioned iterative solvers usually determine the overall convergence rate. However, choosing a good preconditioner for a specific sparse linear system arising from a particular application is the combination of art and science, and presents a formidable challenge for many design engineers and application scientists who do not have much knowledge of preconditioned iterative methods.

We tackled the problem of choosing suitable preconditioners for particular applications from a nontraditional point of view. We used the techniques and ideas in knowledge discovery and data mining to extract useful information and special features from unstructured sparse matrices and analyze the relationship between these features and the solving status of the spearse linear systems generated from these sparse matrices. We have designed an Intelligent Preconditioner Recommendation System, which can provide advice on choosing a high performance preconditioner as well as suitable parameters for a given sparse linear system. This work opened a new research direction for a very important topic in large scale high performance scientific computing.

The performance of the various data mining algorithms applied in the recommendation system is directly related to the set of matrix features used in the system. We have extracted more than 60 features to represent a sparse matrix. We have proposed to use data mining techniques to predict some expensive matrix features like the condition number. We have also proposed to use the combination of the clustering and classification methods to predict the solving status of a sparse linear system. For the preconditioners with multiple parameters, we may predict the possible combinations of the values of the parameters with which a given sparse linear system may be successfully solved. Furthermore, we have proposed an algorithm to find out which preconditioners work best for a certain sparse linear system with what parameters.

Included in

Engineering Commons

Share

COinS