7 papers · 1 filter
On the Growth Factor of Random Matrices
John Urschel
Gaussian elimination is the oldest and most popular method for solving a linear system. Its numerical stability for a given matrix is controlled by the growth factor, a measure of…
Entry growth in Gaussian elimination
Rikhav Shah, John Urschel
Gaussian elimination is one of the oldest algorithms in mathematics, and the most popular method for solving an unstructured linear system. Its stability in finite precision is con…
LU Factorization of Discrete Random Matrices
Samuel Orellana Mateo, John Urschel, Nicholas West
We consider the probability that a discrete random matrix is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is…
What is Jackson's constant?
Rikhav Shah, John Urschel, Nicholas West
We prove a refinement of Jackson's theorem on the approximation of Lipschitz functions by trigonometric polynomials. Our result precisely characterizes the leading error term assoc…
Spectral density estimation for normal matrices
Cameron Musco, Christopher Musco, Rikhav Shah +2
The spectral density estimation problem asks for an algorithm that, given an matrix , outputs a probability measure that is a good approximation to the uniform distr…
On the exponential rate of the condition number of Fourier submatrices and Vandermonde matrices
Rikhav Shah, John Urschel
The discrete Fourier transform matrix is one of the most important matrices in linear algebra, and submatrices of it arise in a variety of applications. Though the discrete Fourier…
The largest 5th pivot may be the root of a 61st degree polynomial
James Chen, Alan Edelman, John Urschel
This paper introduces a number of new techniques in the study of the famous question from numerical linear algebra: what is the largest possible growth factor when performing Gauss…