Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

On solving composite power polynomial equations


Authors: Yingquan Wu and Christoforos N. Hadjicostis
Journal: Math. Comp. 74 (2005), 853-868
MSC (2000): Primary 65H10; Secondary 12Y05
Published electronically: August 20, 2004
MathSciNet review: 2114652
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is well known that a system of power polynomial equations can be reduced to a single-variable polynomial equation by exploiting the so-called Newton's identities. In this work, by further exploring Newton's identities, we discover a binomial decomposition rule for composite elementary symmetric polynomials. Utilizing this decomposition rule, we solve three types of systems of composite power polynomial equations by converting each type to single-variable polynomial equations that can be solved easily. For each type of system, we discuss potential applications and characterize the number of nontrivial solutions (up to permutations) and the complexity of our proposed algorithmic solution.


References [Enhancements On Off] (What's this?)

  • 1. David Dobbs and Robert Hanks, A modern course on the theory of equations, 2nd ed., Polygonal Publ. House, Washington, NJ, 1992. With an appendix by Michael Weinstein. MR 1169295 (93b:12001)
  • 2. Y. Wu and C. N. Hadjicostis, ``Non-concurrent fault detection and identification using encoded Petri net models of discrete event systems,'' Proceedings of the 2002 IEEE Conf. on Decision and Control, vol. 4, pp. 4018-4023, Las Vegas, Nevada, 2002.
  • 3. R. E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, Cambridge, UK, 2002.
  • 4. Dario Bini and Victor Y. Pan, Polynomial and matrix computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412 (95k:65003)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65H10, 12Y05

Retrieve articles in all journals with MSC (2000): 65H10, 12Y05


Additional Information

Yingquan Wu
Affiliation: Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, Illinois 61801
Address at time of publication: 139 Coordinated Science Laboratory, 1308 West Main Street, Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, Illinois 61801-2307
Email: ywu4@uiuc.edu

Christoforos N. Hadjicostis
Affiliation: Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, Illinois 61801
Address at time of publication: 357 Coordinated Science Laboratory, 1308 West Main Street, Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, Illinois 61801-2307
Email: chadjic@uiuc.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01710-7
PII: S 0025-5718(04)01710-7
Keywords: Power polynomial, composite power polynomial, Newton's identities, system of polynomial equations
Received by editor(s): October 9, 2002
Received by editor(s) in revised form: September 5, 2003
Published electronically: August 20, 2004
Additional Notes: This material is based upon work supported in part by the National Science Foundation under NSF Career Award 0092696 and NSF ITR Award 0085917 and in part by the Motorola Research Center at the University of Illinois. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the NSF or Motorola.
Article copyright: © Copyright 2004 American Mathematical Society