Searching for rare growth factors using multicanonical Monte Carlo methods

• Autores: Tobin A. Driscoll, Kara L. Maki
• Localización: SIAM Review, ISSN 0036-1445, Vol. 49, Nº. 4, 2007, págs. 673-692
• Idioma: inglés
• DOI: 10.1137/050637662
• Texto completo no disponible (Saber más ...)
• Resumen

  • The growth factor of a matrix quantifies the amount of potential error growth possible when a linear system is solved using Gaussian elimination with row pivoting. While it is an easy matter [N. J. Higham and D. J. Higham, SIAM J. Matrix Anal. Appl., 10 (1989), pp. 155¿164] to construct examples of $n\times n$ matrices having any growth factor up to the maximum of $2^{n-1}$, the weight of experience and analysis [N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996], [L. N. Trefethen and R. S. Schreiber, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 335¿360], [L. N. Trefethen and I. D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997] suggest that matrices with exponentially large growth factors are exceedingly rare. Here we show how to conduct numerical experiments on random matrices using a multicanonical Monte Carlo method to explore the tails of growth factor probability distributions. Our results suggest, for example, that the occurrence of an $8\times 8$ matrix with a growth factor of 40 is on the order of a once-in-the-age-of-the-universe event.