Accessibility navigation


Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations

Scott, J. and Tuma, M. (2016) Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations. SIAM Journal on Scientific Computing, 38 (6). C603-C623. ISSN 1095-7197

[img]
Preview
Text - Published Version
· Please see our End User Agreement before downloading.

771kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1137/16M105890X

Abstract/Summary

The efficient solution of the normal equations corresponding to a large sparse linear least squares problem can be extremely challenging. Robust incomplete factorization (RIF) preconditioners represent one approach that has the important feature of computing an incomplete LLT factorization of the normal equations matrix without having to form the normal matrix itself. The right-looking implementation of Benzi and T˚uma has been used in a number of studies but experience as shown that in some cases it can be computationally slow and its memory requirements are not known a priori. Here a new left-looking variant is presented that employs a symbolic preprocessing step to replace the potentially expensive searching through entries of the normal matrix. This involves a directed acyclic graph (DAG) that is computed as the computation proceeds. An inexpensive but effective pruning algorithm is proposed to limit the number of edges in the DAG. Problems arising from practical applications are used to compare the performance of the right-looking approach with a left-looking implementation that computes the normal matrix explicitly and our new implicit DAG-based left-looking variant.

Item Type:Article
Refereed:Yes
Divisions:Faculty of Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
ID Code:74695
Publisher:Society for Industrial and Applied Mathematics

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation