r/compsci • u/beeskness420 Algorithmic Evangelist • 5d ago

Research John Urschel 🏈 proves sqrt(n) growth factor for partial pivots

https://arxiv.org/abs/2610.06785
100 Upvotes

95% Upvoted

13 comments sorted by

15

u/beeskness420 Algorithmic Evangelist 5d ago

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 how large entries can become during elimination. In this work, we prove a number of new results regarding the growth factor of random matrices.

First, we provide tight estimates for the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting.

Second, and most notably, we prove that the growth factor of an n×n Gaussian matrix under partial pivoting is rarely much larger than sqrt(n), resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.

4

u/prehensilemullet 5d ago

What does it mean to prove that something is rarely the case?  How does one define “rarely” objectively enough for some kind of proof?

17

u/beeskness420 Algorithmic Evangelist 5d ago edited 5d ago

The formal definition is "with high probability" or "with very high probability", it means with probability 1-o(1). If the failure rate decays exponentially then we say "very".

https://en.wikipedia.org/wiki/With_high_probability

1

u/orangejake 4d ago

important for this making sense is that the proof is relative not to an arbitrary input, but to a distribution over inputs. Relative to this input distribution, the growth factor is itself a random variable, and you can prove e.g. inequalities for this random variable that hold with some probability.

7

u/qpxa 4d ago

Blows my mind to see him both reached the apex of elite disciplines in both professional athletics and academia. Chance of achieving either one by itself is minuscule, this man has done both. One requiring elite physical attributes and the other equally impressive mental acumen.

10

u/Benabik 5d ago

Is 🏈 part of his name? Did he use some technique called 🏈 proof?

23

u/CavemanKnuckles 5d ago

He's an MIT mathematician who played for the Baltimore Ravens. At least, if Wikipedia is to be believed

5

u/ImAFraidKn0t 5d ago

Damn this guy is fly as hell

8

u/beeskness420 Algorithmic Evangelist 5d ago

Anecdotally everyone I know who has met him in person says he's a really great guy too. His episode of My Favorite Theorem is fantastic.

2

u/j15y 5d ago

I can confirm. He's a really nice (and smart) guy!

2

u/Exodus100 4d ago

He’s awesome

1

u/algebratwurst 5d ago

He won’t have time to get all the women

2

u/bythenumbers10 3d ago

He's married, with a daughter, to boot. Good for him!

Too busy swimming in theorems to drown in pussy. Leaves more for the rest of us in /r/compsci.