Smoothed analysis of componentwise condition numbers for sparse matrices

Dennis CHEUNG; Felipe CUCKER

doi:10.1093/imanum/drt068

Smoothed analysis of componentwise condition numbers for sparse matrices

Dennis CHEUNG, Felipe CUCKER^*

^*Corresponding author for this work

Department of Mathematics

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n × n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order (log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.

Original language	English
Pages (from-to)	74-88
Journal	IMA Journal of Numerical Analysis
Volume	35
Issue number	1
Online published	26 Feb 2014
DOIs	https://doi.org/10.1093/imanum/drt068
Publication status	Published - Jan 2015

Research Keywords

condition numbers
loss of precision
smoothed analysis
triangular systems

Access Output

10.1093/imanum/drt068

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{7590d0b9b5b44285afe3d487d7355da5,

title = "Smoothed analysis of componentwise condition numbers for sparse matrices",

abstract = "We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n × n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order (log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.",

keywords = "condition numbers, loss of precision, smoothed analysis, triangular systems",

author = "Dennis CHEUNG and Felipe CUCKER",

year = "2015",

month = jan,

doi = "10.1093/imanum/drt068",

language = "English",

volume = "35",

pages = "74--88",

journal = "IMA Journal of Numerical Analysis",

issn = "0272-4979",

publisher = "Oxford University Press",

number = "1",

}

TY - JOUR

T1 - Smoothed analysis of componentwise condition numbers for sparse matrices

AU - CHEUNG, Dennis

AU - CUCKER, Felipe

PY - 2015/1

Y1 - 2015/1

N2 - We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n × n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order (log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.

AB - We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n × n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order (log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.

KW - condition numbers

KW - loss of precision

KW - smoothed analysis

KW - triangular systems

UR - http://www.scopus.com/inward/record.url?scp=84922583123&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84922583123&origin=recordpage

U2 - 10.1093/imanum/drt068

DO - 10.1093/imanum/drt068

M3 - RGC 21 - Publication in refereed journal

SN - 0272-4979

VL - 35

SP - 74

EP - 88

JO - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

IS - 1

ER -

Smoothed analysis of componentwise condition numbers for sparse matrices

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

GRF: Smoothed Analysis of Componentwise Condition Numbers for Sparse Matrices

Cite this

Smoothed analysis of componentwise condition numbers for sparse matrices

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

GRF: Smoothed Analysis of Componentwise Condition Numbers for Sparse Matrices

Cite this