On présente une relation entre la solution d'un système de Toeplitz biniveaux, Tu = g, et les syzygies de polynômes à deux variables ou hyperplans mobiles. Cette approche nous donne la possibilité de définir les générateurs pour les matrices de Toeplitz biniveaux en utilisant les générateurs du module de syzygie correspondant. On démontre que ce module est généralisé par 8 éléments et que la solution de Tu = g peut être interprétée comme le reste de la division d'un vecteur, dépendant de g, par ces générateurs.
Ce nouveau point de vu de résolution peut être interprété comme une décomposition de Gohberg–Semencul [3, 5] pour les matrices de Toeplitz biniveaux. La difficulté de généraliser la notion de structure de déplacement [2, 4, 3] du cas scalaire (de niveau un) au cas par blocs, et l'absence de notion de générateurs pour les matrices de Toeplitz biniveaux sont à la base de l'absence d'une telle décomposition jusqu'à présent.
L'utilisation de cette idée pour résoudre les systèmes de Toeplitz scalaires nous permet de donner un algorithme de résolution ultra rapide. L'absence de la notion de μ-base pour les modules de syzygies en plusieurs variables complique la situation pour les systèmes de Toeplitz biniveaux, et l'obtention d'un algorithme de résolution ultra rapide utilisant cette approche reste un problème ouvert.
@article{CML_2011__3_2_253_0,
author = {Khalil, Houssam and Mourrain, Bernard and Schatzman, Michelle},
title = {Transformation du probl\`eme de r\'esolution de syst\`emes de {Toeplitz} biniveaux \`a un probl\`eme polynomial},
journal = {Confluentes Mathematici},
pages = {253--262},
publisher = {World Scientific Publishing Co Pte Ltd},
volume = {3},
number = {2},
year = {2011},
doi = {10.1142/S1793744211000357},
language = {fr},
url = {http://www.numdam.org/articles/10.1142/S1793744211000357/}
}
TY - JOUR AU - Khalil, Houssam AU - Mourrain, Bernard AU - Schatzman, Michelle TI - Transformation du problème de résolution de systèmes de Toeplitz biniveaux à un problème polynomial JO - Confluentes Mathematici PY - 2011 SP - 253 EP - 262 VL - 3 IS - 2 PB - World Scientific Publishing Co Pte Ltd UR - http://www.numdam.org/articles/10.1142/S1793744211000357/ DO - 10.1142/S1793744211000357 LA - fr ID - CML_2011__3_2_253_0 ER -
%0 Journal Article %A Khalil, Houssam %A Mourrain, Bernard %A Schatzman, Michelle %T Transformation du problème de résolution de systèmes de Toeplitz biniveaux à un problème polynomial %J Confluentes Mathematici %D 2011 %P 253-262 %V 3 %N 2 %I World Scientific Publishing Co Pte Ltd %U http://www.numdam.org/articles/10.1142/S1793744211000357/ %R 10.1142/S1793744211000357 %G fr %F CML_2011__3_2_253_0
Khalil, Houssam; Mourrain, Bernard; Schatzman, Michelle. Transformation du problème de résolution de systèmes de Toeplitz biniveaux à un problème polynomial. Confluentes Mathematici, Tome 3 (2011) no. 2, pp. 253-262. doi : 10.1142/S1793744211000357. http://www.numdam.org/articles/10.1142/S1793744211000357/
[1] D. Eisenbud, Commutative Algebra, Graduate Texts in Mathematics, Vol. 150 (Springer-Verlag, 1995), with a view toward algebraic geometry.
[2] B. Friedlander, M. Morf, T. Kailath et L. Ljung, New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices, Linear Algebra Appl. 27 (1979) 31–60.
[3] G. Heinig et K. Rost, Algebraic Methods for Toeplitz-like Matrices and Operators, Operator Theory : Advances and Applications, Vol. 13 (Birkhäuser-Verlag, 1984).
[4] T. Kailath, S. Y. Kung et M. Morf, Displacement ranks of matrices and linear equa- tions, J. Math. Anal. Appl. 68 (1979) 395–407.
[5] G. Labahn et T. Shalom, Inversion of Toeplitz matrices with only two standard equa- tions, Linear Algebra Appl. 175 (1992) 143–158.
[6] H. Michael Möller et F. Mora, New constructive methods in classical ideal theory, J. Algebra 100 (1986) 138–178.
[7] B. Mourrain et V. Y. Pan, Multivariate polynomials, duality, and structured matrices, J. Complexity 16 (2000) 110–180, real computation and complexity (Schloss Dagstuhl, 1998).
[8] S. Serra Capizzano et E. Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl. 21 (1999) 431–439.
[9] H. Khalil, B. Mourrain and M. Schatzman, Toeplitz and Toeplitz-block-Toeplitz matrices and their correlation with syzygies of polynomials, in Matrix Methods : The- ory, Algorithms, Applications, International seminar matrix methods and operator equations (MM&OE), eds. V. Olshevsky and E. Tyrtyshnikov (World Scientific, 2008), pp. 296–312.
[10] D. Noutsos, S. S. Capizzano and P. Vassalos, Matrix algebra preconditioners for mul- tilevel Toeplitz systems do not insure optimal convergence rate, Theor. Comput. Sci. 315 (2004) 557–579.
[11] E. Tyrtyshnikov, Fast algorithms for block Toeplitz matrices, Sov. J. Numer. Math. Model. 1 (1985) 121–139.
[12] M. Van Barel, G. Heinig and P. Kravanja, A stabilized superfast solver for nonsym- metric Toeplitz systems, SIAM J. Matrix Anal. Appl. 23 (2001) 494–510.
Cité par Sources :
