×

zbMATH — the first resource for mathematics

A fast Schur-Euclid-type algorithm for quasiseparable polynomials. (English) Zbl 1396.13028
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 341-383 (2017).
Summary: In this paper, a fast \(\mathscr {O}(n^2)\) algorithm is presented for computing recursive triangular factorization of a Bezoutian matrix associated with quasiseparable polynomials via a displacement equation. The new algorithm applies to a fairly general class of quasiseparable polynomials that includes real orthogonal, Szegö polynomials, and several other important classes of polynomials, e.g., those defined by banded Hessenberg matrices. While the algorithm can be seen as a Schur-type for the Bezoutian matrix it can also be seen as a Euclid-type for quasiseparable polynomials via factorization of a displacement equation. The process, i.e., fast Euclid-type algorithm for quasiseparable polynomials or Schur-type algorithm for Bezoutian associated with quasiseparable polynomials, is carried out with the help of a displacement equation satisfied by Bezoutian and Confederate matrices leading to \(\mathscr {O}(n^2)\) complexity.
For the entire collection see [Zbl 1379.13001].
MSC:
13P15 Solving polynomial systems; resultants
12Y05 Computational aspects of field theory and polynomials (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
68W40 Analysis of algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Allen, B.M., Rosenthal, J.: A matrix Euclidean algorithm induced by state space realization. Linear Algebra Appl. 288 , 105-121 (1999) · Zbl 0963.93025
[2] 2. Barnett, S.: Greatest common divisor of two polynomials. Linear Algebra Appl. 3 (1), 7-9 (1970) · Zbl 0191.32503
[3] 3. Barnett, S.: A note on the Bezoutian matrix. SIAM J. Appl. Math. 22 (1), 84-86 (1972) · Zbl 0245.15011
[4] 4. Barnett, S.: A companion matrix analogue for orthogonal polynomials. Linear Algebra Appl. 12 (3), 197-202 (1975) · Zbl 0327.15026
[5] 5. Beckermann, B., Labahn, G.: When are two numerical polynomials relatively prime? J. Symb. Comput. 26 (6), 677-689 (1998) · Zbl 1008.65021
[6] 6. Beckermann, B., Labahn, G.: A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials. J. Symb. Comput. 26 (6), 691-714 (1998) · Zbl 0935.65051
[7] 7. Bella, T., Eidelman, Y., Gohberg, I., Olshevsky V.: Classifications of three-term and two-term recurrence relations via subclasses of quasiseparable matrices. SIAM J. Matrix Anal. · Zbl 1079.65037
[8] 8. Bella, T., Eidelman, Y., Gohberg, I., Olshevsky, V., Tyrtyshnikov, E.: Fast inversion of polynomial-Vandermonde matrices for polynomial systems related to order one quasiseparable matrices. In: Kaashoek, M.A., Rodman, L., Woerdeman, H.J. (eds.) Advances in Structured Operator Theory and Related Areas, Operator Theory: Advances and Applications, vol. 237, pp. 79-106. Springer, Basel (2013) · Zbl 1281.65050
[9] 9. Bella, T., Olshevsky, V., Zhlobich, P.: Classifications of recurrence relations via subclasses of (H, k)-quasiseparable matrices. In: Van Dooren, P., Bhattacharyya, S.P., Chan, R.H., Olshevsky, V., Routray, A. (eds.) Numerical Linear Algebra in Signals, Systems and Control. Lecture Notes in Electrical Engineering, vol. 80, pp. 23-54. Springer, Netherlands (2011) · Zbl 1251.39001
[10] 10. Bini, D.A., Boito, P.: Structured matrix-based methods for polynomial · Zbl 1190.65060
[11] 11. Bini, D.A., Gemignani, L.: Fast parallel computation of the polynomial remainder sequence via Bezout and Hankel matrices. SIAM J. Comput. 24 (1), 63-77 (1995) · Zbl 0818.68092
[12] 12. Bini, D.A., Gemignani, L.: Bernstein-Bezoutian matrices. Theor. Comput. Sci. 315 (2-3), 319-333 (2004) · Zbl 1071.65014
[13] 13. Bitmead, R.R., Kung, S.Y., Anderson, B.D., Kailath, T.: Greatest common divisor via generalized Sylvester and Bezout matrices. IEEE Trans. Autom. Control 23 (6), 1043-1047 (1978) · Zbl 0389.93008
[14] 14. Brown, W.S.: On Euclid’s algorithm and the computation of polynomial greatest common divisors. J. Assoc. Comput. Mach. 18 (4), 478-504 (1971) · Zbl 0226.65040
[15] 15. Brown, W.S., Traub, J.F.: On Euclid’s algorithm and the theory of subresultants. J. Assoc. Comput. Mach. 18 (4), 505-514 (1971) · Zbl 0226.65041
[16] 16. Calvetti, D., Reichel, L.: Fast inversion of vandermondelike matrices involving orthogonal polynomials. BIT Numer. Math. 33 (3), 473-484 (1993) · Zbl 0809.65013
[17] 17. Delosme, J.M., Morf, M.: Mixed and minimal representations for Toeplitz and related systems, In: Proceedings 14th Asilomar Conference on Circuits, Systems, and Computers, Monterey, California (1980)
[18] 18. Dym, H.: Structured matrices, reproducing kernels and interpolation. In: Olshevsky, V. (ed.) Structured Matrices in Mathematics, Computer Science and Engineering I: Contemporary Mathematics, vol. 280, p. 329. American Mathematical Society, Providence (2001) · Zbl 1022.47011
[19] 19. Genin, Y.V.: Euclid algorithm, orthogonal polynomials, and generalized Routh-Hurwitz algorithm. Linear Algebra Appl. 246 , 131-158 (1996) · Zbl 0879.12001
[20] 20. Gohberg, I., Olshevsky, V.: Fast inversion of Chebyshev-Vandermonde matrices. Numer. Math. 67 (1), 71-92 (1994) · Zbl 0791.65013
[21] 21. Gohberg, T., Kailath, T., Olshevsky, V.: Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comput. 64 (212), 1557-1576 (1995) · Zbl 0848.65010
[22] 22. Grenander, U., Szegö, G.: Toeplitz Forms and Applications. University of California Press, Berkeley (1958)
[23] 23. Heinig, G.: Matrix representations of Bezoutians. Linear Algebra Appl. 223-224 , 337-354 (1995) · Zbl 0827.15031
[24] 24. Heinig, G., Olshevsky, V.: The Schur algorithm for matrices with Hessenberg displacement structure. In: Olshevsky, V. (ed.) Structured Matrices in Mathematics, Computer Science, and Engineering II: Contemporary Mathematics, vol. 281, pp. 3-16. American Mathematical Society, Providence (2001) · Zbl 0993.65034
[25] 25. Heinig, G., Rost, K.: Algebraic Methods for Toeplitz-Like Matrices and Operators. Operator Theory: Advances and Applications, vol. 13. Birkhäuser, Basel (1984) · Zbl 0549.15013
[26] 26. Heinig, G., Rost, K.: On the inverses of Toeplitz-plus-Hankel matrices. Linear Algebra Appl. 106 , 39-52 (1988) · Zbl 0646.15015
[27] 27. Heinig, G., Rost, K.: Matrix representations of Toeplitz-plus-Hankel matrix inverses. Linear Algebra Appl. 113 , 65-78 (1989) · Zbl 0663.15009
[28] 28. Heinig, G., Rost, K.: Split algorithm and ZW-factorization for Toeplitz and Toeplitz-plus-Hankel matrices. In: Proceedings of the Fifteenth International Symposium on Mathematical Theory of Networks and Systems, Notre Dame, August 12-16 (2002)
[29] 29. Heinig, G., Rost, K.: New fast algorithms for Toeplitz-plus-Hankel matrices. SIAM J. Matrix Anal. Appl. 25 (3), 842857 (2004) · Zbl 1062.65032
[30] 30. Heinig, G., Rost, K.: Fast algorithms for Toeplitz and Hankel matrices. Linear Algebra Appl. 435 (1), 159 (2011) · Zbl 1211.65035
[31] 31. Kailath, T., Kung, S.Y., Morf, M.: Displacement ranks of matrices and linear equations. J. Math. Anal. Appl. 68 (2), 395407 (1979) · Zbl 0433.15001
[32] 32. Kailath, T., Olshevsky, V.: Displacement-structure approach to polynomial Vandermonde and related matrices. Linear Algebra Appl. 261 , 49-90 (1997) · Zbl 0887.65032
[33] 33. Kailath, T.: Displacement structure and array algorithms. In: Kailath, T., Sayed, A.H. (eds.) Fast Reliable Algorithms for Matrices with Structure. SIAM, Philadelphia (1999)
[34] 34. Kailath, T., Sayed, A.H.: Displacement structure: theory and applications. SIAM Rev. 37 (3), 297-386 (1995) · Zbl 0839.65028
[35] 35. Kaltofen, E., May, J., Yang, Z., Zhi, L.: Approximate factorization of multivariate polynomials using singular value decomposition. J. Symb. Comput. 43 (5), 359-376 (2008) · Zbl 1135.12003
[36] 36. Lancaster, P., Tismenetsky, M.: The Theory of Matrices with Applications, 2nd edn. Academic Press INC., Orlando (1985) · Zbl 0558.15001
[37] 37. Maroulas, J., Barnett, S.: Polynomials with respect to a general basis. I. Theory. J. Math. Anal. Appl. 72 , 177-194 (1979) · Zbl 0426.15011
[38] 38. Morf, M.: Fast Algorithms for Multivariable Systems. Ph. D. Thesis, Stanford University (1974)
[39] 39. Noda, M.T., Sasaki, T.: Approximate GCD and its application to ill-conditioned algebraic equations. J. Comput. Appl. Math. 38 , 335-351 (1991) · Zbl 0747.65034
[40] 40. Olshevsky, V., Stewart, M.: Stable factorization of Hankel and Hankel-like matrices. Numer. Linear Algebra 8 (6-7), 401-434 (2001) · Zbl 1055.65041
[41] 41. Pan, V.Y.: Computation of approximate polynomial GCDs and an extension. Inf. Comput. 167 (2), 71-85 (2001) · Zbl 1005.12004
[42] 42. Pan, V.Y., Tsigaridas, E.: Nearly optimal computations with structured matrices. In: Watt, S.M., Verschelde, J., Zhi, L. (eds.) Proceedings of the International Conference on Symbolic Numeric Computation, China, July 2014, pp. 21-30. ACM Digital Library, New York (2014) · Zbl 1346.68297
[43] 43. Rost, K.: Generalized companion matrices and matrix representations for generalized Bezoutians. Linear Algebra Appl. 193 (1), 151-172 (1993) · Zbl 0798.15007
[44] 44. Wimmer, H.K.: On the history of the Bezoutian and the resultant matrix. Linear Algebra Appl. 128 , 27-34 (1990) · Zbl 0711.15028
[45] 45. Yang, Z.H.: Polynomial Bezoutian matrix with respect to a general basis. Linear Algebra Appl. 331 , 165-179 (2001) · Zbl 0980.15022
[46] 46. Zarowski, C.J.: A Schur Algorithm for Strongly Regular Toeplitz-plus-Hankel Matrices. In: Proceedings of the 33rd Midwest Symposium on Circuits and Systems, Alta, Aug, 1990. IEEE Xplore Digital Library, vol. 1, pp. 556-559. IEEE, New York (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.