Tellegen's principle into practice

ABSTRACT

The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

REFERENCES

• 1: A. Antoniou. Digital Filters: Analysis and Design. McGraw-Hill Book Co., 1979.
• 2: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 3: J. L. Bordewijk. Inter-reciprocity applied to electrical networks. Appl. Sci. Res. B., 6:1--74, 1956.
• 4: P. Bürgisser, M. Clausen, and A. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.
• 5: J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
• 6: C. M. Fiduccia. On obtaining upper bounds on the complexity of matrix multiplication. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 31--40. Plenum, New York, 1972.
• 7: Charles M. Fiduccia, On the algebraic complexity of matrix multiplication., 1973
• 8: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 9: G. Hanrot, M. Quercia, and P. Zimmermann. The middle product algorithm, I. Speeding up the division and square root of power series. Technical report, RR INRIA 4664, 2002.
• 10: Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002 [doi>10.1006/jsco.2002.0562]
• 11: J. Hopcroft and J. Musinski. Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM Journal on Computing, 2:159--173, 1973.
• 12: Erich Kaltofen , Robert M. Corless , David J. Jeffrey, Challenges of symbolic computation: my favorite open problems, Journal of Symbolic Computation, v.29 n.6, p.891-919, June 2000 [doi>10.1006/jsco.2000.0370]
• 13: Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
• 14: Michael Kaminski , David G. Kirkpatrick , Nader H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of Algorithms, v.9 n.3, p.354-364, September 1988 [doi>10.1016/0196-6774(88)90026-0]
• 15: G. Lecerf and É. Schost. Fast multivariate power series multiplication in characteristic zero. SADIO Electronic Journal on Informatics and Operations Research. To appear, manuscript of December 2002.
• 16: Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, University of California at Los Angeles, Los Angeles, CA, 1992
• 17: P. Penfield, Jr., R. Spencer, and S. Duinker. Tellegen's theorem and electrical networks. The M.I.T. Press, Cambridge, Mass.-London, 1970.
• 18: V. Shoup. NTL: A library for doing number theory. http://www.shoup.net.
• 19: Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.14-21, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120697]
• 20: Victor Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, v.20 n.4, p.363-397, October 1995 [doi>10.1006/jsco.1995.1055]
• 21: Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309859]
• 22: B. Tellegen. A general network theorem, with applications. Philips Research Reports, 7:259--269, 1952.
• 23: Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Algorithms, Theory

Keywords:
Tellegen's principle, computer algebra, interpolation, polynomial evaluation, transposition principle