A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386785" target="_blank" >RIV/00216208:11320/18:10386785 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s11075-018-0478-2" target="_blank" >https://doi.org/10.1007/s11075-018-0478-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11075-018-0478-2" target="_blank" >10.1007/s11075-018-0478-2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

Popis výsledku v původním jazyce

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (A(s) and A(d)) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix A(s)(T) A(s) is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of A(s) and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.

Název v anglickém jazyce

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

Popis výsledku anglicky

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (A(s) and A(d)) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix A(s)(T) A(s) is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of A(s) and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.

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/GC17-04150J" target="_blank" >GC17-04150J: Robustní dvojúrovňové simulace založené na Fourierově metodě a metodě konečných prvků: Odhady chyb, redukované modely a stochastika</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

Numerical Algorithms

ISSN

1017-1398

e-ISSN

—

Svazek periodika

79

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

1147-1168

Kód UT WoS článku

000450947500008

EID výsledku v databázi Scopus

2-s2.0-85041206179