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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331039" target="_blank" >RIV/00216208:11320/16:10331039 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/16M105890X" target="_blank" >http://dx.doi.org/10.1137/16M105890X</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/16M105890X" target="_blank" >10.1137/16M105890X</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

The ecient 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 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 eective 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.

Název v anglickém jazyce

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

Popis výsledku anglicky

The ecient 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 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 eective 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/LL1202" target="_blank" >LL1202: Materiály s implicitními konstitutivními vztahy: Od teorie přes redukci modelů k efektivním numerickým metodám</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal of Scientific Computing

ISSN

1064-8275

e-ISSN

—

Svazek periodika

38

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

21

Strana od-do

"C603"-"C623"

Kód UT WoS článku

000391853100001

EID výsledku v databázi Scopus

2-s2.0-85007049715