17 papers
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…
Nodal Count for Orthogonally Invariant Ensembles
Lior Alon, Dan Mikulincer, John Urschel
We investigate the nodal count of eigenvectors of random matrices interpreted as operators on signed complete graphs. Our focus is on orthogonally invariant ensembles, with particu…
On the Maximum Spread of Non-Negative Matrices
Susie Lu, John Urschel
Given a directed graph , the spread of is the largest distance between any two eigenvalues of its adjacency matrix. In 2022, Breen, Riasanovsky, Tait, and Urschel asked what…
A Class of Optimal Directed Graphs for Network Synchronization
Susie Lu, John Urschel, Ji Liu
In a paper by Nishikawa and Motter, a quantity called the normalized spread of the Laplacian eigenvalues is used to measure the synchronizability of certain network dynamics. Throu…
Estimating the numerical range with a Krylov subspace
Cecilia Chen, John Urschel
Krylov subspace methods are a powerful tool for efficiently solving high-dimensional linear algebra problems. In this work, we study the approximation quality that a Krylov subspac…
On the Frobenius norm of the inverse of a non-negative matrix
Elsa Frankel, John Urschel
We prove a new lower bound for the Frobenius norm of the inverse of an non-negative matrix. This bound is only a modest improvement over previous results, but is sufficient for ful…
On a perturbation analysis of Higham squared maximum Gaussian elimination growth matrices
Alan Edelman, John Urschel, Bowen Zhu
Gaussian elimination is the most popular technique for solving a dense linear system. Large errors in this procedure can occur in floating point arithmetic when the matrix's growth…
Average Nodal Count and the Nodal Count Condition for Graphs
Lior Alon, John Urschel
The nodal edge count of an eigenvector of the Laplacian of a graph is the number of edges on which it changes sign. This quantity extends to any real symmetric matrix s…
Recovering a Magnitude-Symmetric Matrix from its Principal Minors
Victor-Emmanuel Brunel, John Urschel
We consider the inverse problem of finding a magnitude-symmetric matrix (matrix with opposing off-diagonal entries equal in magnitude) with a prescribed set of principal minors. Th…
A New Upper Bound For the Growth Factor in Gaussian Elimination with Complete Pivoting
Ankit Bisain, Alan Edelman, John Urschel
The growth factor in Gaussian elimination measures how large the entries of an LU factorization can be relative to the entries of the original matrix. It is a key parameter in erro…
Estimating the matrix norm
Larry Guth, Dominique Maldague, John Urschel
The matrix norm is a fundamental quantity appearing in a variety of areas of mathematics. This quantity is known to be efficiently computable in only a few specia…