A geometrical approach to finding multivariate approximate LCMs and GCDs. (English) Zbl 1337.65033
Summary: In this article we present a new approach to compute an approximate least common multiple (LCM) and an approximate greatest common divisor (GCD) of two multivariate polynomials. This approach uses the geometrical notion of principal angles whereas the main computational tools are the Implicitly Restarted Arnoldi method and sparse QR decomposition. Upper and lower bounds are derived for the largest and smallest singular values of the highly structured Macaulay matrix. This leads to an upper bound on its condition number and an upper bound on the 2-norm of the product of two multivariate polynomials. Numerical examples are provided.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 15A42 | Inequalities involving eigenvalues and eigenvectors |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F50 | Computational methods for sparse matrices |
Keywords:
approximate LCM; approximate GCD; multivariate polynomials; principal angles; singular values; Arnoldi iterationSoftware:
SuiteSparseQRReferences:
| [1] | Barnett, S., Polynomials and Linear Control Systems (1983), M. Dekker: M. Dekker New York · Zbl 0528.93003 |
| [2] | Stoica, P.; Söderström, T., Common factor detection and estimation, Automatica, 33, 985-989 (1996) · Zbl 0881.93076 |
| [3] | Unnikrishna Pillai, S.; Liang, B., Blind image deconvolution using a robust GCD approach, IEEE Trans. Image Process., 8, 2, 295-301 (1999) |
| [4] | Karmarkar, N.; Lakshman, Y. N., On Approximate GCDs of univariate polynomials, J. Symbolic Comput., 26, 6, 653-666 (1998) · Zbl 0967.12007 |
| [5] | Schönhage, A., Quasi-GCD computations, J. Complexity, 1, 1, 118-137 (1985) · Zbl 0586.68031 |
| [6] | Emiris, I. Z.; Galligo, A.; Lombardi, H., Certified approximate univariate GCDs, J. Pure Appl. Algebra, 117-118, 0, 229-251 (1997) · Zbl 0891.65015 |
| [7] | R.M. Corless, P.M. Gianni, B.M. Trager, S.M. Watt, The singular value decomposition for polynomial systems, in: ACM International Symposium on Symbolic and Algebraic Computation, 1995, pp. 195-207. · Zbl 0920.65034 |
| [8] | Noda, M.-T.; Sasaki, T., Approximate GCD and its application to ill-conditioned equations, J. Comput. Appl. Math., 38, 1-3, 335-351 (1991) · Zbl 0747.65034 |
| [9] | Z. Zeng, B.H. Dayton, The approximate GCD of inexact polynomials Part I: a univariate algorithm, preprint, 2004. · Zbl 1134.13313 |
| [10] | Corless, R.; Watt, S.; Zhi, L., QR factoring to compute the GCD of univariate approximate polynomials, IEEE Trans. Signal Process., 52, 12, 3394-3402 (2004) · Zbl 1372.65120 |
| [11] | Diaz-Toca, G. M.; Gonzalez-Vega, L., Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases, Linear Algebra Appl., 412, 2-3, 222-246 (2006) · Zbl 1084.65037 |
| [12] | González-Vega, L., An elementary proof of Barnett’s theorem about the greatest common divisor of several univariate polynomials, Linear Algebra Appl., 247, 0, 185-202 (1996) · Zbl 0866.12002 |
| [13] | Winkler, J. R.; Lao, X., The calculation of the degree of an approximate greatest common divisor of two polynomials, J. Comput. Appl. Math., 235, 6, 1587-1603 (2011) · Zbl 1246.65062 |
| [14] | Kaltofen, E.; May, J. P.; Yang, Z.; Zhi, L., Approximate factorization of multivariate polynomials using singular value decomposition, J. Symbolic Comput., 43, 5, 359-376 (2008) · Zbl 1135.12003 |
| [15] | Z. Zeng, The approximate GCD of inexact polynomials part II: a multivariate algorithm, in: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, 2004, pp. 320-327. · Zbl 1134.13313 |
| [16] | MATLAB R2011a, The Mathworks Inc., Natick, Massachusetts, 2011. |
| [17] | Cox, D. A.; Little, J. B.; O’Shea, D., Ideals, Varieties and Algorithms (2007), Springer-Verlag · Zbl 1118.13001 |
| [18] | Björck, R.; Golub, G. H., Numerical methods for computing angles between linear subspaces, Math. Comp., 27, 123, 579-594 (1973) · Zbl 0282.65031 |
| [19] | Lehoucq, R. B.; Sorensen, D. C., Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl., 17, 4, 789-821 (1996) · Zbl 0863.65016 |
| [20] | Davis, T. A., Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse qr factorization, ACM Trans. Math. Software, 38, 1, 1-22 (2011) · Zbl 1365.65122 |
| [21] | Schur, I., Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen, J. Reine Angew. Math., 140, 1-28 (1911) · JFM 42.0367.01 |
| [22] | Beauzamy, B.; Bombieri, E.; Enflo, P.; Montgomery, H., Products of polynomials in many variables, J. Number Theory, 36, 2, 219-245 (1990) · Zbl 0729.30004 |
| [23] | Johnson, C. R., A Gershgorin-type lower bound for the smallest singular value, Linear Algebra Appl., 112, 1-7 (1989) · Zbl 0723.15013 |
| [24] | Zeng, Z., ApaTools: a software toolbox for approximate polynomial algebra, (Stillman, M.; Verschelde, J.; Takayama, N., Software for Algebraic Geometry. Software for Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 148 (2008), Springer: Springer New York), 149-167 · Zbl 1148.68581 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
