Li, Xin; Moreno Maza, Marc; Schost, Éric Fast arithmetic for triangular sets: from theory to practice. (English) Zbl 1183.68755 J. Symb. Comput. 44, No. 7, 891-907 (2009). Summary: 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. Cited in 6 Documents MSC: 68W30 Symbolic computation and algebraic computation 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) Keywords:fast polynomial arithmetic; triangular set; high-performance computing Software:SPIRAL; RegularChains; Magma; Maple; CUMODP; AXIOM PDFBibTeX XMLCite \textit{X. Li} et al., J. Symb. Comput. 44, No. 7, 891--907 (2009; Zbl 1183.68755) Full Text: DOI References: [1] Aubry, P.; Lazard, D.; Moreno Maza, M., On the theories of triangular sets, J. Symbolic Comput., 28, 1,2, 45-124 (1999) · Zbl 0943.12003 [2] Bini, D., Relations between exact and approximate bilinear algorithms. Applications, Calcolo, 17, 1, 87-97 (1980) · Zbl 0459.65028 [3] Bini, D.; Capovani, M.; Romani, F.; Lotti, G., \(O(n^{2.7799})\) complexity for \(n \times n\) approximate matrix multiplication, Inform. Process. Lett., 8, 5, 234-235 (1979) · Zbl 0395.68048 [4] Bini, D.; Lotti, G.; Romani, F., Approximate solutions for the bilinear form computational problem, SIAM J. Comput., 9, 4, 692-697 (1980) · Zbl 0446.68035 [5] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 [6] Bostan, A.; Schost, É., On the complexities of multipoint evaluation and interpolation, Theoret. Comput. Sci., 329, 1-3, 223-235 (2004) · Zbl 1086.68150 [7] Cantor, D. G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Inform., 28, 7, 693-701 (1991) · Zbl 0766.68055 [8] Cook, S., 1966. On the minimum computation time of functions. Ph.D. Thesis, Harvard University; Cook, S., 1966. On the minimum computation time of functions. Ph.D. Thesis, Harvard University [9] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2002), McGraw-Hill [10] Dahan, X.; Moreno Maza, M.; Schost, É.; Wu, W.; Xie, Y., Lifting techniques for triangular decompositions, (ISSAC’05 (2005), ACM), 108-115 · Zbl 1360.14146 [11] Filatei, A.; Li, X.; Moreno Maza, M.; Schost, É., Implementation techniques for fast polynomial arithmetic in a high-level programming environment, (ISSAC’06 (2006), ACM), 93-100 [12] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press · Zbl 0936.11069 [13] van der Hoeven, J., The Truncated Fourier Transform and applications, (ISSAC’04 (2004), ACM), 290-296 · Zbl 1064.65158 [14] Johnson, J. R.; Krandick, W.; Lynch, K.; Richardson, K. G.; Ruslanov, A. D., High-performance implementations of the Descartes method, (ISSAC’06 (2006), ACM), 154-161 [15] Johnson, J. R.; Krandick, W.; Ruslanov, A. D., Architecture-aware classical Taylor shift by 1, (ISSAC’05 (2005), ACM), 200-207 · Zbl 1360.68938 [16] Kung, H. T., On computing reciprocals of power series, Numer. Math., 22, 341-348 (1974) · Zbl 0274.65009 [17] Langemyr, L., Algorithms for a multiple algebraic extension, (Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Progr. Math., vol. 94 (1991), Birkhäuser), 235-248 · Zbl 0741.11053 [18] Lazard, D., Solving zero-dimensional algebraic systems, J. Symbolic Comput., 13, 2, 147-160 (1992) · Zbl 0753.13013 [19] Lemaire, F., Moreno Maza, M., Xie, Y., 2005. The; Lemaire, F., Moreno Maza, M., Xie, Y., 2005. The · Zbl 1114.68628 [20] Li, X.; Moreno Maza, M.; Schost, É., Fast arithmetic for triangular sets: From theory to practice, (ISSAC’07 (2007), ACM), 269-276 · Zbl 1190.68093 [21] Li, X.; Moreno Maza, M., Efficient implementation of polynomial arithmetic in a multiple-level programming environment, (ICMS’06 (2006), Springer), 12-23 · Zbl 1229.12008 [22] van Hoeij, M.; Monagan, M., A modular GCD algorithm over number fields presented with multiple extensions, (ISSAC’02 (2002), ACM), 109-116 · Zbl 1072.68705 [23] Montgomery, P. L., Modular multiplication without trial division, Math. Comp., 44, 170, 519-521 (1985) · Zbl 0559.10006 [24] Moreno Maza, M., 1999. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK. http://www.csd.uwo.ca/ moreno/; Moreno Maza, M., 1999. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK. http://www.csd.uwo.ca/ moreno/ [25] Pan, V. Y., Simple multivariate polynomial multiplication, J. Symbolic Comput., 18, 3, 183-186 (1994) · Zbl 0831.12004 [26] Püschel, M.; Moura, J. M.F.; Johnson, J.; Padua, D.; Veloso, M.; Singer, B. W.; Xiong, J.; Franchetti, F.; Gačić, A.; Voronenko, Y.; Chen, K.; Johnson, R. W.; Rizzolo, N., SPIRAL: Code generation for DSP transforms, Proc’ IEEE, 93, 2, 232-275 (2005) [27] Schönhage, A., Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Inform., 7, 395-398 (1977) · Zbl 0362.65011 [28] Schönhage, A.; Strassen, V., Schnelle Multiplikation großer Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 [29] Schost, É., Multivariate power series multiplication, (ISSAC’05 (2005), ACM), 293-300 · Zbl 1360.68955 [30] Shoup, V., A new polynomial factorization algorithm and its implementation, J. Symbolic Comput., 20, 4, 363-397 (1995) · Zbl 0854.11074 [31] Sieveking, M., An algorithm for division of powerseries, Computing, 10, 153-156 (1972) · Zbl 0251.68023 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.