no. 12
Numerical Analysis
Upper bounds on the distribution of the condition number of singular matrices
[Bornes supérieures pour la fonction de distribution du conditionnement des matrices singulières]

Présenté par : Philippe G. Ciarlet

Beltrán, Carlos1 ; Pardo, Luis Miguel1
1 Departamento de Matemáticas, Estadística y Computación, F. de Ciencias, Universidad de Cantabria, 39071 Santander, Spain
Comptes Rendus. Mathématique, Tome 340 (2005) no. 12, pp. 915-919.

Nous exhibons des bornes de la fonction de distribution du conditionnement des matrices singulières. Pour ce but nous developpons une technique nouvelle pour analyser les volumes des tubes (par rapport a la distance de Fubini–Study) autour des sous-variétés algèbriques d'un espace projectif complex. Plus spécifiquement, nous demontrons des bornes supérieueres de volumes des intersections des tubes extrinsèques (autour des sous-variétés algébriques avec une autre variété algèbrique donnée).

We exhibit upper bounds for the probability distribution of the generalized condition number of singular complex matrices. To this end, we develop a new technique to study volumes of tubes about projective varieties in the complex projective space. As a main outcome, we show an upper bound estimate for the volume of the intersection of a tube with an equi-dimensional projective algebraic variety.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2005.05.012
Beltrán, Carlos 1 ; Pardo, Luis Miguel 1

1 Departamento de Matemáticas, Estadística y Computación, F. de Ciencias, Universidad de Cantabria, 39071 Santander, Spain 
@article{CRMATH_2005__340_12_915_0,
     author = {Beltr\'an, Carlos and Pardo, Luis Miguel},
     title = {Upper bounds on the distribution of the condition number of singular matrices},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {915--919},
     publisher = {Elsevier},
     volume = {340},
     number = {12},
     year = {2005},
     doi = {10.1016/j.crma.2005.05.012},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2005.05.012/}
}
TY  - JOUR
AU  - Beltrán, Carlos
AU  - Pardo, Luis Miguel
TI  - Upper bounds on the distribution of the condition number of singular matrices
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 915
EP  - 919
VL  - 340
IS  - 12
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2005.05.012/
DO  - 10.1016/j.crma.2005.05.012
LA  - en
ID  - CRMATH_2005__340_12_915_0
ER  - 
%0 Journal Article
%A Beltrán, Carlos
%A Pardo, Luis Miguel
%T Upper bounds on the distribution of the condition number of singular matrices
%J Comptes Rendus. Mathématique
%D 2005
%P 915-919
%V 340
%N 12
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2005.05.012/
%R 10.1016/j.crma.2005.05.012
%G en
%F CRMATH_2005__340_12_915_0
Beltrán, Carlos; Pardo, Luis Miguel. Upper bounds on the distribution of the condition number of singular matrices. Comptes Rendus. Mathématique, Tome 340 (2005) no. 12, pp. 915-919. doi : 10.1016/j.crma.2005.05.012. http://www.numdam.org/articles/10.1016/j.crma.2005.05.012/

[1] Castro, D.; Montaña, J.L.; Pardo, L.M.; San Martín, J. The distribution of condition numbers of rational data of bounded bit length, Found. Comput. Math., Volume 2 (2002), pp. 1-52

[2] Demmel, J.W. The probability that a numerical analysis problem is difficult, Math. Comp., Volume 50 (1988), pp. 449-480

[3] Eckart, C.; Young, G. The approximation of one matrix by another of lower rank, Psychometrika, Volume 1 (1936), pp. 211-218

[4] Edelman, A. Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., Volume 9 (1988), pp. 543-560

[5] Edelman, A. On the distribution of a scaled condition number, Math. Comp., Volume 58 (1992), pp. 185-190

[6] Fulton, W. Intersection Theory, Ergeb. Math. Grenzgeb. (3) [Results in Mathematics and Related Areas (3)], vol. 2, Springer-Verlag, Berlin, 1984

[7] Golub, G.H.; Van Loan, C.F. Matrix Computations, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 1996

[8] Gray, A. Volumes of tubes about complex submanifolds of complex projective space, Trans. Amer. Math. Soc., Volume 291 (1985), pp. 437-449

[9] Gray, A. Tubes, Progr. Math., vol. 221, Birkhäuser, Basel, 2004

[10] Heintz, J. Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., Volume 24 (1983), pp. 239-277

[11] Higham, N.J. Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002

[12] W. Kahan, Huge generalized inverses of rank-deficient matrices, Unpublished manuscript

[13] Mirsky, L. Results and problems in the theory of doubly-stochastic matrices, Z. Wahrscheinlichkeitstheorie Verw. Gebiete, Volume 1 (1962/1963), pp. 319-334

[14] Schmidt, E. Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Tiel. Entwicklung willkurlichen Funktionen nach System vorgeschriebener, Maht. Ann., Volume 63 (1907), pp. 433-476

[15] Smale, S. On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.), Volume 13 (1985), pp. 87-121

[16] Stewart, G.W.; Sun, J.G. Matrix Perturbation Theory, Computer Sci. Sci. Comput., Academic Press, Boston, MA, 1990

[17] Trefethen, L.N.; Bau, D. Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997

[18] Turing, A.M. Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math., Volume 1 (1948), pp. 287-308

[19] von Neumann, J.; Goldstine, H.H. Numerical inverting of matrices of high order, Bull. Amer. Math. Soc., Volume 53 (1947), pp. 1021-1099

[20] Weyl, A. On the volume of tubes, Amer. J. Math., Volume 61 (1939), pp. 461-472

[21] Wilkinson, J.H. The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965

Cité par Sources :

⁎ Research was partially supported by MTM2004-01167.