zbMATH — the first resource for mathematics

On the complexity of multivariate polynomial division. (English) Zbl 1383.68039
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 447-458 (2017).
Summary: In this paper, we present a new algorithm for reducing a multivariate polynomial with respect to an autoreduced tuple of other polynomials. In a suitable sparse complexity model, it is shown that the execution time is essentially the same (up to a logarithmic factor) as the time needed to verify that the result is correct.
For the entire collection see [Zbl 1379.13001].
68Q25 Analysis of algorithms and problem complexity
12Y05 Computational aspects of field theory and polynomials (MSC2010)
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
13P05 Polynomials, factorization in commutative rings
68W30 Symbolic computation and algebraic computation
68W40 Analysis of algorithms
Full Text: DOI
[1] 1. Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 301-309, New York, NY, USA, 1988. ACM Press
[2] 2. Canny, J., Kaltofen, E., Lakshman, Y.: Solving systems of non-linear polynomial equations faster. In: Proceedings of ISSAC ’89, pp. 121-128, Portland, Oregon, A.C.M., New York, 1989. ACM Press
[3] 3. Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 , 297-301 (1965) · Zbl 0127.09002
[4] 4. Fischer, M.J., Stockmeyer, L.J.: Fast on-line integer multiplication. In: Proceedings of 5th ACM Symposium on Theory of Computing, vol. 9, pp. 67-72 (1974) · Zbl 0289.68016
[5] 5. Grigoriev, D.Y., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In: Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pp. 166-172 (1987)
[6] 6. van der Hoeven, J.: Lazy multiplication of formal power series. In: Küchlin, W.W. (ed.) Proceedings of ISSAC ’97, pp. 17-20. Maui, Hawaii, July 1997 · Zbl 0932.68135
[7] 7. van der Hoeven, J.: Relax, but don’t be too lazy. JSC 34 , 479-542 (2002) · Zbl 1011.68189
[8] 8. van der Hoeven, J.: Relaxed multiplication using the middle product. In: Bronstein, M. (ed.) Proceedings of ISSAC ’03, pp. 143-147, Philadelphia, USA, August 2003 · Zbl 1072.68706
[9] 9. van der Hoeven, J.: The truncated Fourier transform and applications. In: Gutierrez, J. (ed.) Proceedings of ISSAC 2004, pp. 290-296, Univ. of Cantabria, Santander, Spain, July 4-7, 2004 · Zbl 1064.65158
[10] 10. van der Hoeven, J.: New algorithms for relaxed multiplication. JSC 42 (8), 792-802 (2007) · Zbl 1130.68103
[11] 11. van der Hoeven, J.: From implicit to recursive equations. Technical report, HAL. · Zbl 1137.35329
[12] 12. van der Hoeven, J., Lecerf, G.: On the complexity of blockwise polynomial multiplication. In: Proceedings of ISSAC ’12, pp. 211-218, Grenoble, France, July 2012 · Zbl 1308.68199
[13] 13. van der Hoeven, J., Lecerf, G.: On the bit-complexity of sparse polynomial multiplication. JSC 50 , 227-254 (2013) · Zbl 1261.65017
[14] 14. van der Hoeven, J., Schost, É.: Multi-point evaluation in higher dimensions. AAECC 24 (1), 37-52 (2013) · Zbl 1280.68303
[15] 15. Kaltofen, E., Lakshman, Y.N.: Improved sparse multivariate polynomial interpolation algorithms. In: ISSAC ’88: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 467-474. Springer (1988)
[16] 16. Robbiano, L.: Term orderings on the polynominal ring. Eur. Conf. Comput. Algebra 2 , 513-517 (1985)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.