Entrywise Approximation for Matrix Inversion and Linear Systems

We study the bit complexity of inverting diagonally dominant matrices, which are associated with random walk quantities such as hitting times and escape probabilities. Such quantities can be exponentially small, even on undirected unit-weighted graphs. However, their nonnegativity suggests that they...

Disgrifiad llawn

Manylion Llyfryddiaeth

Prif Awduron:	Ghadiri, Mehrdad, Nguyen, Hoai-An, Yang, Junzhao
Fformat:	Erthygl
Cyhoeddwyd:	2025
Pynciau:	Data Structures and Algorithms Numerical Analysis 65Y20, 65F10, 65F05, 15A09 G.1.3; F.2.1
Mynediad Ar-lein:	https://arxiv.org/abs/2504.19054 http://arxiv.org/abs/2504.19054
Tagiau:	Ychwanegu Tag Dim Tagiau, Byddwch y cyntaf i dagio'r cofnod hwn!