Alin Bostan
ABSTRACT
It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previously-known one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential operators can be multiplied in nearly optimal time. Theoretical results are validated by intensive experiments.
- Bernstein, D. J. Fast multiplication and its applications. To appear in Buhler-Stevenhagen Algorithmic number theory. http://cr.yp.to/papers.html#multappsGoogle Scholar
- Bostan, A., Chyzak, F., Le Roux, N. Skew-polynomial products by evaluation and interpolation, in preparation.Google Scholar
- Bostan, A., Chyzak, F., Li, Z., Salvy, B. Common multiples of linear ordinary differential and difference operators, in preparation.Google Scholar
- Bostan, A., Schost, É., August 2005. Polynomial evaluation and interpolation on special sets of points. Journal of Complexity 21 (4), 420--446. Google ScholarDigital Library
- Cantor, D. G., Kaltofen, E., 1991. On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28 (7), 693--701. Google ScholarDigital Library
- Chyzak, F. http://algo.inria.fr/chyzak/mgfun.html.Google Scholar
- Coppersmith, D., Winograd, S., Mar. 1990. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9 (3), 251--280. Google ScholarDigital Library
- von zur Gathen, J., Gerhard, J., 1997. Fast algorithms for Taylor shifts and certain difference equations. In: Proceedings of ISSAC'97. ACM Press, New York, pp. 40--47. Google ScholarDigital Library
- von zur Gathen, J., Gerhard, J., 1999. Modern computer algebra. Cambridge University Press. Google ScholarDigital Library
- Gerhard, J., 2000. Modular algorithms for polynomial basis conversion and greatest factorial factorization. In: RWCA'00. pp. 125--141.Google Scholar
- van der Hoeven, J., 2002. FFT-like multiplication of linear differential operators. Journal of Symbolic Computation 33 (1), 123--127. Google ScholarDigital Library
- Kaporin, I., 2004. The aggregation and cancellation techniques as a practical tool for faster matrix multiplication. Theor. Comput. Sci. 315 (2-3), 469--510. Google ScholarDigital Library
- Schönhage, A., Strassen, V., 1971. Schnelle Multiplikation großer Zahlen. Computing 7, 281--292.Google Scholar
- Strassen, V., 1969. Gaussian elimination is not optimal. Numerische Mathematik 13, 354--356.Google ScholarDigital Library
- Takayama, N. http://www.math.kobe-u.ac.jp/KAN/.Google Scholar
Index Terms
- Products of ordinary differential operators by evaluation and interpolation
Recommendations
Characterization of self-adjoint ordinary differential operators
Symmetric differential expressions @? of order n=2k with real valued coefficients give rise to self adjoint operators in the space of weighted square integrable functions. Characterization theorems exist in the literature that describe such self-adjoint ...
Numerical Analysis: Quasilinearization and the estimation of differential operators from eigenvalues
Given a linear ordinary differential operator containing several unknown constants and a number of its eigenvalues, the values of the unknown constants are estimated. A precise formulation is provided, and an effective numerical procedure for solution ...
Real linear quaternionic differential operators
The renewed interest in searching for quaternionic deviations of standard (complex) quantum mechanics resulted, in the last years, in a better understanding of the quaternionic mathematical tools needed to solve quantum mechanical problems. In ...
Comments