Geodesic
Root-squaring with DPR1 matrices
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVII, Tome 373 (2009), pp. 189-193 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Recent progress in polynomial root-finding relies on employing the associated companion and generalized companion DPR1 matrices. (“DPR1” stands for “diagonal plus rank-one.”) We propose an algorithm that uses nearly linear arithmetic time to square a DPR1 matrix. Consequently the algorithm squares the roots of the associated characteristic polynomial. This incorporates the classical techniques of polynomial root-finding by means of root-squaring into new effective framework. Our approach is distinct from the earlier fast methods for squaring companion matrices. Bibl. – 13 titles. 
@article{ZNSL_2009_373_a11,
     author = {V. Y. Pan},
     title = {Root-squaring with {DPR1} matrices},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {189--193},
     year = {2009},
     volume = {373},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a11/}
}
TY  - JOUR
AU  - V. Y. Pan
TI  - Root-squaring with DPR1 matrices
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2009
SP  - 189
EP  - 193
VL  - 373
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a11/
LA  - en
ID  - ZNSL_2009_373_a11
ER  - 
%0 Journal Article
%A V. Y. Pan
%T Root-squaring with DPR1 matrices
%J Zapiski Nauchnykh Seminarov POMI
%D 2009
%P 189-193
%V 373
%U http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a11/
%G en
%F ZNSL_2009_373_a11
V. Y. Pan. Root-squaring with DPR1 matrices. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVII, Tome 373 (2009), pp. 189-193. http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a11/

[1] D. A. Bini, L. Gemignani, V. Y. Pan, “Inverse Power and Durand/Kerner Iteration for Univariate Polynomial Root-finding”, Computers and Mathematics with Applications, 47:2–3 (2004), 447–459 | DOI | MR | Zbl

[2] D. A. Bini, L. Gemignani, V. Y. Pan, “Improved Initialization of the Accelerated and Robust QR-like Polynomial Root-finding”, Electronic Transactions on Numerical Analysis, 17 (2004), 195–205 | MR | Zbl

[3] D. A. Bini, L. Gemignani, V. Y. Pan, “Fast and Stable QR Eigenvalue Algorithms for Generalized Companion Matrices and Secular Equation”, Numerische Math., 3 (2005), 373–408 | DOI | MR | Zbl

[4] J. P. Cardinal, “On Two Iterative Methods for Approximating the Roots of a Polynomial”, Proceedings of AMS-SIAM Summer Seminar: Mathematics of Numerical Analysis: Real Number Algorithms (Park City, Utah, 1995), Lect. Appl. Math., 32, eds. J. Renegar, M. Shub, S. Smale, Amer. Math. Soc., Providence, Rhode Island, 1996, 165–188 | MR | Zbl

[5] S. Fortune, “An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials”, J. Symb. Computat., 33:5 (2002), 627–646 | DOI | MR | Zbl

[6] A. S. Householder, “Dandelin, Lobatchevskii or Gräffe?”, Amer. Math. Monthly, 66 (1959), 464–466 | DOI | MR | Zbl

[7] A. S. Householder, The Theory of Matrices in Numerical Analysis, Dover, New York, 1964 | MR

[8] F. Malek, R. Vaillancourt, “Polynomial Zerofinding Iterative Matrix Algorithms”, Computers and Math. with Applications, 29:1 (1995), 1–13 | DOI | MR | Zbl

[9] F. Malek, R. Vaillancourt, “A Composite Polynomial Zerofinding Matrix Algorithm”, Computers and Math. with Applications, 30:2 (1995), 37–47 | DOI | MR | Zbl

[10] V. Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhäuser, Boston; Springer, New York, 2001 | MR

[11] V. Y. Pan, “Univariate Polynomials: Nearly Optimal Algorithms for Factorization and Rootfinding”, J. Symb. Computat., 33:5 (2002), 701–733 | DOI | MR | Zbl

[12] V. Y. Pan, “Amended DSeSC Power Method for Polynomial Root-finding”, Computers and Math. with Applications, 49:9–10 (2005), 1515–1524 | DOI | MR | Zbl

[13] V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Wang, X. Yan, “Root-finding with Eigen-solving”, Chapter 14, Symbolic-Numeric Computation, eds. Dongming Wang, Li-Hong Zhi, Birkhäuser, Basel–Boston, 2007, 219–245 | MR