More on solving systems of power equations

Wu, Yingquan

doi:10.1090/S0025-5718-10-02363-X

More on solving systems of power equations
HTML articles powered by AMS MathViewer

by Yingquan Wu PDF

Math. Comp. 79 (2010), 2317-2332 Request permission

Abstract:

It is known that a system of power equations can be reduced to a single-variable polynomial equation by exploiting the so-called Newton’s identities. In this work, we investigate four new types of power equation systems. In the first two types we allow the powers to be a mix of positive and negative terms, whereas in the literature the system of power equations involves only positive powers. The first type involves only positive signs of powers, whereas the second type expands to involve both positive and negative signs. We present algebraic methods to solve the system and furthermore fully characterize the number of nontrivial solutions. The other two types are defined over finite fields and otherwise are the same as the conventional system of power equations. The methodology for solving the third type can be viewed as a generalization of the Berlekamp algorithm. The solution space of the last system is fully characterized despite the fact that the number of equations is two less than the number of unknowns.

References

E. R. Berlekamp, Algebraic Coding Theory, Rev. Ed., Laguna Hills, CA: Aegean Park Press, 1984.
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, DOI 10.1007/978-1-4612-0265-3
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
Gui Liang Feng and Kenneth K. Tzeng, A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes, IEEE Trans. Inform. Theory 37 (1991), no. 5, 1274–1287. MR 1136665, DOI 10.1109/18.133246
Ron M. Roth and Paul H. Siegel, Lee-metric BCH codes and their application to constrained and partial-response channels, IEEE Trans. Inform. Theory 40 (1994), no. 4, 1083–1096. MR 1301420, DOI 10.1109/18.335966
Klaus Schiefermayr, Inverse polynomial images which consists of two Jordan arcs—an algebraic solution, J. Approx. Theory 148 (2007), no. 2, 148–157. MR 2362448, DOI 10.1016/j.jat.2007.03.003
Yingquan Wu and Christoforos N. Hadjicostis, On solving composite power polynomial equations, Math. Comp. 74 (2005), no. 250, 853–868. MR 2114652, DOI 10.1090/S0025-5718-04-01710-7
—, “Decoding algorithm and architecture for BCH codes under the Lee metric,” IEEE Trans. Communications, vol. 56, pp. 2050–2059, Dec. 2008.
Yingquan Wu and Christoforos N. Hadjicostis, Algebraic approaches for fault identification in discrete-event systems, IEEE Trans. Automat. Control 50 (2005), no. 12, 2048–2053. MR 2186276, DOI 10.1109/TAC.2005.860249