Xin Li
ABSTRACT
We study arithmetic operations for triangular families of polynomials, concentrating on multiplication in dimension zero. By a suitable extension of fast univariate Euclidean division, we obtain theoretical and practical improvements over a direct recursive approach; for a family of special cases, we reach quasi-linear complexity. The main outcome we have in mind is the acceleration of higher-level algorithms, by interfacing our low-level implementation with languages such as AXIOM or Maple We show the potential for huge speed-ups, by comparing two AXIOM implementations of van Hoeij and Monagan's modular GCD algorithm.
- D. Bini. Relations between exact and approximate bilinear algorithms. Applications.Calcolo, 17(1):87--97, 1980.Google Scholar
Cross Ref
- D. Bini, M. Capovani, F. Romani, and G. Lotti. O(n
2.7799) complexity for n x n approximate matrix multiplication. Inf. Proc. Lett., 8(5):234--235, 1979.Google ScholarCross Ref
- D. Bini, G. Lotti, and F. Romani. Approximate solutions for the bilinear form computational problem. SIAM J. Comput., 9(4):692--697, 1980.Google ScholarDigital Library
- W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235--265, 1997. Google ScholarDigital Library
- D.G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693--701, 1991. Google ScholarDigital Library
- S. Cook. On the minimum computation time of functions. PhD thesis, Harvard University, 1966.Google Scholar
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill, 2002. Google ScholarDigital Library
- X. Dahan, M. Moreno Maza, É. Schost, W. Wu, and Y. Xie. Lifting techniques for triangular decompositions. In ISSAC'05, pages 108--115. ACM, 2005. Google ScholarDigital Library
- A. Filatei, X. Li, M. Moreno Maza, and É. Schost. Implementation techniques for fast polynomial arithmetic in a high-level programming environment. In ISSAC'06, pages 93--100. ACM, 2006. Google ScholarDigital Library
- J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999. Google ScholarDigital Library
- J.R. Johnson, W. Krandick, K. Lynch, K.G. Richardson, and A.D. Ruslanov. High-performance implementations of the Descartes method. In ISSAC'06, pages 154--161. ACM, 2006. Google ScholarDigital Library
- J.R. Johnson, W. Krandick, and A.D. Ruslanov. Architecture-aware classical taylor shift by 1. In ISSAC'05, pages 200--207. ACM, 2005. Google ScholarDigital Library
- H.T. Kung. On computing reciprocals of power series. Numerische Mathematik, 22:341--348, 1974.Google ScholarDigital Library
- L. Langemyr. Algorithms for a multiple algebraic extension. In Effective methods in algebraic geometry), volume94 of Progr. Math., pages 235--248. Birkhäuser, 1991.Google Scholar
- F. Lemaire, M. Moreno Maza, and Y. Xie. The RegularChains library. In Ilias S. Kotsireas, editor, Maple Conference 2005, pages 355--368, 2005.Google Scholar
- X. Li. Low-level techniques for Montgomery multiplication, 2007. http://www.csd.uwo.ca/People/gradstudents/xli96/Google Scholar
- X. Li and M. Moreno Maza. Efficient implementation of polynomial arithmetic in a multiple-level programming environment. In ICMS'06, pages 12--23. Springer, 2006. Google ScholarDigital Library
- M. van Hoeij and M. Monagan. A modular GCD algorithm over number fields presented with multiple extensions. In ISSAC'02, pages 109--116. ACM, 2002. Google ScholarDigital Library
- P.L. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519--521, 1985.Google ScholarCross Ref
- M. Moreno Maza. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK, 1999. http://www.csd.uwo.ca/~moreno/Google Scholar
- V.Y. Pan. Simple multivariate polynomial multiplication. J. Symbolic Comput., 18(3):183--186, 1994. Google ScholarDigital Library
- M. Püschel, J.M.F. Moura, J. Johnson, D. Padua, M. Veloso, B.W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R.W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proc 'IEEE, 93(2):232--275, 2005.Google ScholarCross Ref
- A. Schönhage. Schnelle Multiplikation von Polynomenüber Körpern der Charakteristik 2. Acta Informatica, 7:395--398, 1977.Google ScholarDigital Library
- A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281--292, 1971.Google ScholarCross Ref
- É. Schost. Multivariate power series multiplication. In ISSAC'05, pages 293--300. ACM, 2005. Google ScholarDigital Library
- V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comp., 20(4):363--397, 1995. Google ScholarDigital Library
- M. Sieveking. An algorithm for division of powerseries. Computing, 10:153--156, 1972.Google ScholarCross Ref
Index Terms
- Fast arithmetic for triangular sets: from theory to practice
Recommendations
Fast arithmetic for triangular sets: From theory to practice
We study arithmetic operations for triangular families of polynomials, concentrating on multiplication in dimension zero. By a suitable extension of fast univariate Euclidean division, we obtain theoretical and practical improvements over a direct ...
Relaxed Hensel lifting of triangular sets
In this paper, we present a new lifting algorithm for triangular sets over general p-adic rings. Our contribution is to give, for any p-adic triangular set, a shifted algorithm of which the triangular set is a fixed point. Then we can apply the relaxed ...
High-Speed Arithmetic Arrays
High-speed multifunction arithmetic arrays for multiplication, division, square and square-root operations are presented in this paper. These arrays seem attractive due to their versatility and speed. A recently described quotient-bit evaluation ...
Comments