Abstract
Resultants characterize the existence of roots of systems of polynomial equations, while their matrix formulae reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has introduced the sparse resultant, which takes into account the sparse structure of the polynomials, as expressed by the respective supports or Newton polytopes. Sparse resultant, or Newton, matrices generalize Macaulay’s matrix and define nontrivial multiples of the sparse resultant from which the latter can be recovered. We exploit their structure with the objective to decrease the complexity of constructing such matrices and of computing the exact resultant. Our present study of these structured matrices implies substantial progress in this direction. Subsequent application of fast matrix-by-vector multiplication shall lead to computational complexity bounds that are roughly quadratic in the matrix size, whereas the existing methods have cubic complexity. Our auxiliary techniques for testing exact and numerical nonsingularity of rectangular matrices may be of some independent interest. Finally, we establish complexity bounds, linear in the number of nonzero terms, for polynomial multiplication, under our model of sparseness.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, andJ.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.
D.N. Bernstein,The number of roots of a system of equations, Funct. Anal. and Appl.9(2), (1975) 183–185.
D. Bini, V.Y. Pan, Polynomial and Matrix Computations, volume 1: Fundamental Algorithms, Birkhäuser, Boston, 1994.
J.F. Canny, The Complexity of Robot Motion Planning, M.I.T. Press, Cambridge, Mass., 1988.
J. Canny, I. Emiris,An efficient algorithm for the sparse mixed resultant, In G. Cohen, T. Mora, and O. Moreno, editors, Proc. Intern. Symp. Applied Algebra, Algebraic Algor. and Error-Corr. Codes, LNCS 263, pages 89–104, Puerto Rico, 1993. Springer.
J.F. Canny, E. Kaltofen, Y. Lakshman,Solving systems of non-linear polynomial equations faster, In Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation, pages 121–128, 1989.
I.Z. Emiris, J.F. Canny,Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Computation20(2), (August 1995) 117–149.
E. Ehrart,Sur un problème de géométrie diophantienne, I. Polyèdres et réseaux, J. Reine Angew. Math.226, (1967) 1–29.
I.Z. Emiris,Sparse Elimination and Applications in Kinematics, PhD thesis, Computer Science Division, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, December 1994.
I.Z. Emiris,On the complexity of sparse elimination, J. Complexity12, (1996) 134–166.
I.Z. Emiris, V.Y. Pan,The structure of sparse resultant matrices, In Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation, 1997, to appear.
I.M. Gelfand, M.M. Kapranov, A.V. Zelevinsky,Hyperdeterminants, Advances in Math.96(2), 1992.
G.H. Golub, C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, Maryland, 1989.
A.G. Khovanskii, Fewnomials, AMS Press, Providence, Rhode Island, 1991.
E. Kaltofen, Y. Lakshman,Improved sparse multivariate polynomial interpolation algorithms, In Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation, volume 358 of LNCS, pages 467–474. Springer, 1988.
E. Kaltofen, V.Y. Pan,Processor Efficient Parallel Solution of Linear Systems over an Abstract Field, Proc. 3rd Ann. ACM Symp. on Parallel Algorithms and Architectures, pages 180–191, ACM Press, New York, 1991.
E. Kaltofen, B.D. Saunders,On Wiedemann’s method for solving sparse linear systems, In Proc. Intern. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS, volume 536, pages 29–38. Springer, 1991.
B. Mourrain, V.Y. Pan Solving special polynomial systems by using structured matrices and algebraic residues, In F. Cucker and M. Shub, editors, Foundations of Computational Mathematics, LNCS, pages 287–304. Springer, 1997.
B. Mourrain, V.Y. Pan,Multidimensional structured matrices and polynomial systems, Calcolo, this volume.
V.Y. Pan,Numerical computation of a polynomial GCD and extensions. Research Report 2969, INRIA Sophia Antipolis, France, 1996.
V.Y. Pan,Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Theor. Comp. Science162(2), (1996) 173–223.
B.N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, 1980.
P. Pedersen, B. Sturmfels,Product formulas for resultants and Chow forms, Math. Zeitschrift214, (1993) 377–396.
N.N. Vasiliev,Evaluations of sparse polynomials and the synthesis evaluating programs, In Intern. Conf. on Comp. Algebra and Appl. Theor. Phys. Dubna, 1984.
B.L. van der Waerden, Modern Algebra, F. Ungar Publishing Co., New York, 3rd edition, 1950.
D.H. Wiedemann,Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory32(1), (1986) 54–62.
R. Zippel, Effective Polynomial Computation, Kluwer Academic Publishers, Boston, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Emiris, I.Z., Pan, V.Y. Techniques for exploiting structure in matrix formulae of the sparse resultant. Calcolo 33, 353–369 (1996). https://doi.org/10.1007/BF02576009
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02576009