×

zbMATH — the first resource for mathematics

Computing nearby non-trivial Smith forms. (English) Zbl 1452.65084
Summary: We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank).
We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple.

MSC:
65F60 Numerical computation of matrix exponential and similar matrix functions
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmad, S.; Alam, R., Pseudospectra, critical points and multiple eigenvalues of matrix polynomials, Linear Algebra Appl., 430, 4, 1171-1195 (2009) · Zbl 1168.15007
[2] Beckermann, B.; Labahn, G., When are two numerical polynomials relatively prime?, J. Symb. Comput., 26, 677-689 (1998) · Zbl 1008.65021
[3] Beelen, T.; Van Dooren, P., An improved algorithm for the computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., 105, 9-65 (1988) · Zbl 0645.65022
[4] Bertsekas, D., Nonlinear Programming (1999), Athena Scientific: Athena Scientific USA
[5] Braatz, R. P.; Young, P. M.; Doyle, J. C.; Morari, M., Computational complexity of μ calculation, IEEE Trans. Autom. Control, 39, 5, 1000-1002 (1994) · Zbl 0807.93020
[6] Demmel, J.; Kågström, B., The generalized Schur decomposition of an arbitrary pencil \(A - \lambda B\): robust software with error bounds and applications. Part I: theory and algorithms, ACM Trans. Math. Softw., 19, 2, 160-174 (1993) · Zbl 0889.65042
[7] Demmel, J.; Kågström, B., The generalized Schur decomposition of an arbitrary pencil \(A - \lambda\) B: robust software with error bounds and applications. Part II: software and applications, ACM Trans. Math. Softw., 19, 2, 175-201 (1993) · Zbl 0889.65043
[8] Demmel, J. W.; Edelman, A., The dimension of matrices (matrix pencils) with given Jordan (Kronecker) canonical forms, Linear Algebra Appl., 230, 61-87 (1995) · Zbl 0842.15011
[9] Edelman, A.; Elmroth, E.; Kågström, B., A geometric approach to perturbation theory of matrices and matrix pencils. Part I: versal deformations, SIAM J. Matrix Anal. Appl., 18, 3, 653-692 (1997) · Zbl 0873.15006
[10] Edelman, A.; Elmroth, E.; Kågström, B., A geometric approach to perturbation theory of matrices and matrix pencils. Part II: a stratification-enhanced staircase algorithm, SIAM J. Matrix Anal. Appl., 20, 3, 667-699 (1999) · Zbl 0940.65040
[11] Fan, J.-Y.; Yuan, Y.-X., On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74, 1, 23-39 (2005) · Zbl 1076.65047
[12] Fatouros, S.; Karcanias, N., Resultant properties of gcd of many polynomials and a factorization representation of gcd, Int. J. Control, 76, 16, 1666-1683 (2003) · Zbl 1043.93017
[13] Giesbrecht, M.; Haraldson, J.; Kaltofen, E., Computing approximate greatest common right divisors of differential polynomials, Found. Comput. Math. (2019), In press
[14] Giesbrecht, M.; Haraldson, J.; Labahn, G., Computing the nearest rank-deficient matrix polynomial, (Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC’17). Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC’17), Kaiserslautern, Germany (2017)), 181-188
[15] Giesbrecht, M.; Haraldson, J.; Labahn, G., Computing nearby non-trivial Smith forms, (Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’18). Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’18), New York, USA (2018)), 159-166
[16] Giesbrecht, M.; Haraldson, J.; Labahn, G., Lower rank approximations of matrix polynomials, J. Symb. Comput. (2019), In press
[17] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials (2009), SIAM: SIAM USA
[18] Golub, G.; Van Loan, C., Matrix Computations, vol. 3 (2012), Johns Hopkins University Press: Johns Hopkins University Press USA
[19] Haraldson, J., Computing Approximate GCRDs of Differential Polynomials (2015), Cheriton School of Computer Science, University of Waterloo, Master’s thesis · Zbl 1345.68283
[20] Haraldson, J., Matrix Polynomials and Their Lower Rank Approximations (2019), Cheriton School of Computer Science, University of Waterloo, PhD thesis
[21] Higham, N. J., Accuracy and Stability of Numerical Algorithms, vol. 80 (2002), SIAM
[22] Hoffman, A. J., On approximate solutions of systems of linear inequalities, J. Res. Natl. Bur. Stand., 49, 4 (1952)
[23] Kailath, T., Linear Systems, vol. 156 (1980), Prentice-Hall: Prentice-Hall USA
[24] Kaltofen, E.; Storjohann, A., The complexity of computational problems in exact linear algebra, (Encyclopedia of Applied and Computational Mathematics (2015), Springer: Springer Germany), 227-233
[25] Kaltofen, E.; Yang, Z.; Zhi, L., Structured low rank approximation of a Sylvester matrix, (Symbolic-Numeric Computation. Trends in Mathematics (2007), Birkhäuser Verlag: Birkhäuser Verlag Basel, Switzerland), 69-83 · Zbl 1117.65060
[26] Karmarkar, N.; Lakshman, Y. N., Approximate polynomial greatest common divisors and nearest singular polynomials, (Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’96) (1996), ACM Press: ACM Press Zurich, Switzerland), 35-39 · Zbl 0928.13017
[27] Lasserre, J.-B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[28] Lossers, O., Solution to problem 73-17: a Hadamard-type bound on the coefficients of a determinant of polynomials, SIAM Rev., 16, 3, 394-395 (1974)
[29] Magnus, J.; Neudecker, H., Matrix Differential Calculus with Applications in Statistics and Econometrics (1988), Wiley · Zbl 0651.15001
[30] Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-hard, Math. Control Signals Syst., 6, 1, 1-9 (1993) · Zbl 0780.93027
[31] Stewart, G., Perturbation theory for rectangular matrix pencils, Linear Algebra Appl., 208, 297-301 (1994) · Zbl 0806.15012
[32] Van Dooren, P., The computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., 27, 103-140 (1979) · Zbl 0416.65026
[33] Van Dooren, P.; Dewilde, P., The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl., 50, 545-579 (1983) · Zbl 0507.65008
[34] Vardulakis, A.; Stoyle, P., Generalized resultant theorem, IMA J. Appl. Math., 22, 3, 331-335 (1978) · Zbl 0403.12025
[35] Wright, S., An algorithm for degenerate nonlinear programming with rapid local convergence, SIAM J. Optim., 15, 3, 673-696 (2005) · Zbl 1077.90067
[36] Yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, (Topics in Numerical Analysis (2001), Springer), 239-249 · Zbl 1001.65047
[37] Zeng, Z.; Dayton, B. H., The approximate GCD of inexact polynomials, (Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’04). Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’04), Santander, Spain (2004)), 320-327 · Zbl 1134.13313
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.