Saddle points in random matrices: analysis of Knuth search algorithms
Hofri, Micha; Jacquet, Philippe
DateDecember 22, 1997
In this note we present an analysis of algorithms for finding saddle points in a random matrix, presented by Donald E. Knuth as exercise 1.3.2-12 in The Art of Computer Programming. We estimate the average computing costs of three saddle point search algorithms. Amusingly, the asymptotic results in this analysis about matrix saddle points uses the same approach that leads to the celebrated saddle point method in complex analysis.