Recycling Preconditioners for Sequences of Linear Systems and Matrix Reordering
| dc.contributor.author | Li, Ming | en |
| dc.contributor.committeechair | de Sturler, Eric | en |
| dc.contributor.committeemember | Lin, Tao | en |
| dc.contributor.committeemember | Beattie, Christopher A. | en |
| dc.contributor.committeemember | Gugercin, Serkan | en |
| dc.contributor.department | Mathematics | en |
| dc.date.accessioned | 2015-12-26T09:07:50Z | en |
| dc.date.available | 2015-12-26T09:07:50Z | en |
| dc.date.issued | 2015-12-09 | en |
| dc.description.abstract | In science and engineering, many applications require the solution of a sequence of linear systems. There are many ways to solve linear systems and we always look for methods that are faster and/or require less storage. In this dissertation, we focus on solving these systems with Krylov subspace methods and how to obtain effective preconditioners inexpensively. We first present an application for electronic structure calculation. A sequence of slowly changing linear systems is produced in the simulation. The linear systems change by rank-one updates. Properties of the system matrix are analyzed. We use Krylov subspace methods to solve these linear systems. Krylov subspace methods need a preconditioner to be efficient and robust. This causes the problem of computing a sequence of preconditioners corresponding to the sequence of linear systems. We use recycling preconditioners, which is to update and reuse existing preconditioner. We investigate and analyze several preconditioners, such as ILU(0), ILUTP, domain decomposition preconditioners, and inexact matrix-vector products with inner-outer iterations. Recycling preconditioners produces cumulative updates to the preconditioner. To reduce the cost of applying the preconditioners, we propose approaches to truncate the cumulative preconditioner updates, which is a low-rank matrix. Two approaches are developed. The first one is to truncate the low-rank matrix using the best approximation given by the singular value decomposition (SVD). This is effective if many singular values are close to zero. If not, based on the ideas underlying GCROT and recycling, we use information from an Arnoldi recurrence to determine which directions to keep. We investigate and analyze their properties. We also prove that both truncation approaches work well under suitable conditions. We apply our truncation approaches on two applications. One is the Quantum Monte Carlo (QMC) method and the other is a nonlinear second order partial differential equation (PDE). For the QMC method, we test both truncation approaches and analyze their results. For the PDE problem, we discretize the equations with finite difference method, solve the nonlinear problem by Newton's method with a line-search, and utilize Krylov subspace methods to solve the linear system in every nonlinear iteration. The preconditioner is updated by Broyden-type rank-one updates, and we truncate the preconditioner updates by using the SVD finally. We demonstrate that the truncation is effective. In the last chapter, we develop a matrix reordering algorithm that improves the diagonal dominance of Slater matrices in the QMC method. If we reorder the entire Slater matrix, we call it global reordering and the cost is O(N^3), which is expensive. As the change is geometrically localized and impacts only one row and a modest number of columns, we propose a local reordering of a submatrix of the Slater matrix. The submatrix has small dimension, which is independent of the size of Slater matrix, and hence the local reordering has constant cost (with respect to the size of Slater matrix). | en |
| dc.description.degree | Ph. D. | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:6397 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/64382 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | sequence of linear systems | en |
| dc.subject | updating preconditioners | en |
| dc.subject | inexact Krylov subspace methods | en |
| dc.subject | matrix reordering | en |
| dc.title | Recycling Preconditioners for Sequences of Linear Systems and Matrix Reordering | en |
| dc.type | Dissertation | en |
| thesis.degree.discipline | Mathematics | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | doctoral | en |
| thesis.degree.name | Ph. D. | en |
Files
Original bundle
1 - 1 of 1