Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Saddle Points in Random Matrices: Analysis of Knuth Search Algorithms
| |
|
Saddle Points in Random Matrices: Analysis of Knuth Search Algorithms
M. Hofri1 and P. Jacquet2
| (1) |
Department of Computer Science, WPI, Worcester, MA 01609-2280, USA. hofri@cs.wpi.edu., US |
| (2) |
INRIA, Domaine de Voluceau - Rocquencourt, B.P. 105, 78153 Le Chesnay Cedex, France. Philippe.Jacquet@inria.fr., FR |
Abstract. 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.
Key words. Matrix saddle point, Search, Probabilistic analysis.
Received December 22, 1997; revised March 15, 1998.
Fulltext Preview (Small, Large)
|
|
|
|
|
|