ePubs

The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/24059257
Record Status Checked
Record Id 24059257
Title Preconditioning of linear least squares by RIF for implicitly held normal equations
Contributors
Abstract 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 Tuma has been used in a number of studies but experience has shown that 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 on-the-y. 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.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords
Funding Information
Related Research Object(s): 30627157 , 30692683
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Preprint RAL Preprints RAL-P-2016-001, SIAM J Sci Comput 2016. RAL-P-2016-001.pdf 2016