On the complexity of skew arithmetic. (English) Zbl 1352.68305
Summary: In this paper, we study the complexity of several basic operations on linear differential operators with polynomial coefficients. As in the case of ordinary polynomials, we show that these complexities can be expressed almost linearly in terms of the cost of multiplication.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 12E15 | Skew fields, division rings |
| 12H20 | Abstract differential equations |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
linear differential operators; algorithm; complexity; multiplication; local solution; division; gcrd; lclmSoftware:
MathemagixReferences:
| [1] | Aho, A.V., Steiglitz, K., Ullman, J.D.: Evaluating polynomials on a fixed set of points. SIAM J. Comput. 4, 533-539 (1975) · Zbl 0326.65027 · doi:10.1137/0204045 |
| [2] | Benoit, A., Bostan, A., van der Hoeven, J.: Quasi-optimal multiplication of linear differential operators. In Proceedings of FOCS ’12, pp. 524-530. IEEE, New Brunswick (2012) |
| [3] | Borodin, A., Moenck, R.T.: Fast modular transforms. J. Comput. Syst. Sci. 8, 366-386 (1974) · Zbl 0302.68064 · doi:10.1016/S0022-0000(74)80029-2 |
| [4] | Bostan, A.: Algorithmique efficace pour des opérations de base en calcul formel. Ph.D. Thesis, École polytechnique (2003) · Zbl 1360.13003 |
| [5] | Bostan, A.; Chyzak, F.; Roux, N.; Rafael Sendra, J. (ed.); González-Vega, L. (ed.), Products of ordinary differential operators by evaluation and interpolation, 23-30 (2008), Linz/Hagenberg · Zbl 1297.65050 · doi:10.1145/1390768.1390775 |
| [6] | Bostan, A., Chyzak, F., Salvy, B., Li, Z.: Fast computation of common left multiples of linear ordinary differential operators. In: van der Hoeven, J., van Hoeij, M. (eds.) Proceedings of ISSAC ’12, pp. 99-106. Grenoble, France (2012) · Zbl 1323.68585 |
| [7] | Bostan, A., Schost, É.: Polynomial evaluation and interpolation on special sets of points. J. Complex. 21(4), 420-446 (2005). Festschrift for the 70th Birthday of Arnold Schönhage · Zbl 1101.68039 |
| [8] | Brassine, E.: Analogie des équations différentielles linéaires à coefficients variables, avec les équations algébriques, pp. 331-347. Note III du Tome 2 du Cours d’analyse de Ch. Sturm. École polytechnique (1864) · Zbl 0003.20104 |
| [9] | Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inf. 28, 693-701 (1991) · Zbl 0766.68055 · doi:10.1007/BF01178683 |
| [10] | 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 · doi:10.1090/S0025-5718-1965-0178586-1 |
| [11] | Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the 19th Annual Symposium on Theory of Computing, pp. 1-6. New York City (1987) · Zbl 0702.65046 |
| [12] | Demidov, S.S.: On the history of the theory of linear differential equations. Arch. Hist. Exact. Sci. 28(4), 369-387 (1983) · Zbl 0542.01005 · doi:10.1007/BF00328044 |
| [13] | Giesbrecht, M.: Factoring in skew polynomial rings over finite fields. In: Proceedings of LATIN ’92, Volume 583 of LNCS, pp. 191-203 (1992) · Zbl 0766.68055 |
| [14] | Giesbrecht, M.: Factoring in skew polynomial rings over finite finite fields. JSC 26, 463-486 (1998) · Zbl 0941.68160 |
| [15] | Giesbrecht, M., Zhang, Y.: Factoring and decomposing ore polynomials over \[\mathbb{F}_q (t)\] Fq(t). In: Bronstein, M. (ed.) Proceedings of ISSAC ’03, pp. 127-134. Philadelphia, USA (2003) · Zbl 1072.68670 |
| [16] | Grigoriev, D.Y.: Complexity of factoring and calculating the GCD of linear ordinary differential operators. J. Symb. Comput. 10(1), 7-37 (1990) · Zbl 0728.68067 · doi:10.1016/S0747-7171(08)80034-X |
| [17] | Heffter, L.: Über gemeinsame Vielfache linearer Differentialausdrücke und lineare Differentialgleichungen derselben Klasse. J. Reine Angew. Math. 116, 157-166 (1896) · JFM 27.0244.01 |
| [18] | Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of ISSAC 2014, pp. 296-303. Kobe, Japan (2014) · Zbl 1325.65061 |
| [19] | Li, Z.: A subresultant theory for ore polynomials with applications. In: Gloor, O. (ed.) Proceedings of ISSAC ’98, pp. 132-139. Rostock, Germany (1998) · Zbl 0922.16015 |
| [20] | Libri, G.: Mémoire sur la résolution des équations algébriques dont les racines ont entre elles un rapport donné, et sur l’intégration des équations différentielles linéaires dont les intégrales particulières peuvent s’exprimer les unes par les autres. J. Reine Angew. Math. 10, 167-194 (1833) · ERAM 010.0373cj · doi:10.1515/crll.1833.10.167 |
| [21] | Moenck, R.T., Borodin, A.: Fast modular transforms via division. In: Thirteenth Annual IEEE Symposium on Switching and Automata Theory, pp. 90-96. Univ. Maryland, College Park, MD (1972) · Zbl 0326.65027 |
| [22] | Ore, O.: Theorie der linearen Differentialgleichungen. J. Reine Angew. Math. 167, 221-234 (1932) · Zbl 0003.20104 |
| [23] | Ore, O.: Theory of non-commutative polynomials. Ann. Math. 34(3), 480-508 (1933) · Zbl 0007.15101 · doi:10.2307/1968173 |
| [24] | Pan, V.: How to Multiply Matrices Faster, Volume 179 of Lect. Notes in Math. Springer, Berlin (1984) · Zbl 0548.65022 · doi:10.1007/3-540-13866-8 |
| [25] | Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf. 7, 395-398 (1977) · Zbl 0362.65011 · doi:10.1007/BF00289470 |
| [26] | Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7, 281-292 (1971) · Zbl 0223.68007 · doi:10.1007/BF02242355 |
| [27] | Stanley, R.P.: Differentially finite power series. Eur. J. Comb. 1, 175-188 (1980). MR #81m:05012 · Zbl 0445.05012 · doi:10.1016/S0195-6698(80)80051-5 |
| [28] | Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13, 352-356 (1969) · Zbl 0185.40101 · doi:10.1007/BF02165411 |
| [29] | Strassen, V.: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20, 238-251 (1973) · Zbl 0251.65036 · doi:10.1007/BF01436566 |
| [30] | van der Hoeven, J.: FFT-like multiplication of linear differential operators. JSC 33(1), 123-127 (2002) · Zbl 1006.16029 |
| [31] | van der Hoeven, J.: Relax, but don’t be too lazy. JSC 34, 479-542 (2002) · Zbl 1011.68189 |
| [32] | van der Hoeven, J.: Relaxed multiplication using the middle product. In: Bronstein, M. (ed.) Proceedings of ISSAC ’03, pp. 143-147. Philadelphia, USA (2003) · Zbl 1072.68706 |
| [33] | van der Hoeven, J.: On the complexity of skew arithmetic. Technical Report, HAL (2011). http://hal.archives-ouvertes.fr/hal-00557750 · Zbl 1352.68305 |
| [34] | van der Hoeven, J., Lecerf, G., Mourrain, B., et al.: Mathemagix (2002). http://www.mathemagix.org |
| [35] | von zur Gathen, J., Gerhard, J.: Mod. Comput. Algebra, 2nd edn. Cambridge University Press, Cambridge (2002) |
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.
