SPARSE STRETCHING FOR SOLVING SPARSE-DENSE LINEAR LEAST-SQUARES PROBLEMS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10405985" target="_blank" >RIV/00216208:11320/19:10405985 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=gvtlyhyp8s" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=gvtlyhyp8s</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

SPARSE STRETCHING FOR SOLVING SPARSE-DENSE LINEAR LEAST-SQUARES PROBLEMS

Popis výsledku v původním jazyce

Large-scale linear least-squares problems arise in a wide range of practical applications. In some cases, the system matrix contains a small number of dense rows. These make the problem significantly harder to solve because their presence limits the direct applicability of sparse matrix techniques. In particular, the normal matrix is (close to) dense, making a Cholesky factorization impractical. One way to help overcome the dense row problem is to employ matrix stretching. Stretching is a sparse matrix technique that improves sparsity by making the least-squares problem larger. We show that standard stretching can still result in the normal matrix for the stretched problem having an unacceptably large amount of fill. This motivates us to propose a new sparse stretching strategy that performs the stretching so as to limit the fill in the normal matrix and its Cholesky factor. Numerical examples from real problems are used to illustrate the potential gains.

Název v anglickém jazyce

SPARSE STRETCHING FOR SOLVING SPARSE-DENSE LINEAR LEAST-SQUARES PROBLEMS

Popis výsledku anglicky

Large-scale linear least-squares problems arise in a wide range of practical applications. In some cases, the system matrix contains a small number of dense rows. These make the problem significantly harder to solve because their presence limits the direct applicability of sparse matrix techniques. In particular, the normal matrix is (close to) dense, making a Cholesky factorization impractical. One way to help overcome the dense row problem is to employ matrix stretching. Stretching is a sparse matrix technique that improves sparsity by making the least-squares problem larger. We show that standard stretching can still result in the normal matrix for the stretched problem having an unacceptably large amount of fill. This motivates us to propose a new sparse stretching strategy that performs the stretching so as to limit the fill in the normal matrix and its Cholesky factor. Numerical examples from real problems are used to illustrate the potential gains.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2019

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

41

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

"A1604"-"A1625"

Kód UT WoS článku

000473033300010

EID výsledku v databázi Scopus

2-s2.0-85071649703