More Web Proxy on the site http://driver.im/

research-article

Factoring linear differential operators in n variables

Authors:

Mark Giesbrecht,

Viktor LevandovskyyAuthors Info & Claims

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Pages 194 - 201

https://doi.org/10.1145/2608628.2608667

Published: 23 July 2014 Publication History

Abstract

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial nth Weyl algebra, the polynomial nth shift algebra, and Zⁿ-graded polynomials in the nth <u>q</u>-Weyl algebra.

The most unexpected result is that this noncommutative problem of factoring partial differential operators can be approached effectively by reducing it to the problem of solving systems of polynomial equations over a commutative ring. In the case where a given polynomial is Zⁿ-graded, we can reduce the problem completely to factoring an element in a commutative multivariate polynomial ring.

The implementation in Singular is effective on a broad range of polynomials and increases the ability of computer algebra systems to address this important problem. We compare the performance and output of our algorithm with other implementations in major computer algebra systems on nontrivial examples.

References

[1]

S. Abramov. Problems of computer algebra involved in the search for polynomial solutions of linear differential and difference equations. Mosc. Univ. Comput. Math. Cybern., 1989(3):63--68, 1989.

[2]

S. Abramov and M. Petkovšek. On polynomial solutions of linear partial differential and (q-)difference equations. In Proc. CASC 2012, pages 1--11. Berlin: Springer, 2012.

Digital Library

[3]

S. A. Abramov, M. Bronstein, and M. Petkovšek. On polynomial solutions of linear operator equations. In Proc. ISSAC 1995, pages 290--296. ACM Press, 1995.

Digital Library

[4]

D. Andres. Noncommutative Computer Algebra with Applications in in Algebraic Analysis. PhD thesis, RWTH Aachen University, 2013.

[5]

O. Bachmann and H.-G. Gräbe. The symbolicdata project. In Reports on Computer Algebra, volume 27. 2000.

[6]

R. Beals and E. A. Kartashova. Constructively factoring linear partial differential operators in two variables. Theor. Math. Phys., 145(2):1511--1524, 2005.

[7]

B. Buchberger. Introduction to Groebner bases. Berlin: Springer, 1997.

[8]

J. Bueso, J. Gómez-Torrecillas, and A. Verschoren. Algorithmic methods in non-commutative algebra. Applications to quantum groups. Dordrecht: Kluwer Academic Publishers, 2003.

[9]

W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3-1-6 --- A computer algebra system for polynomial computations. 2012. http://www.singular.uni-kl.de.

[10]

M. Foupouagnigni, W. Koepf, and A. Ronveaux. Factorization of fourth-order differential equations for perturbed classical orthogonal polynomials. J. Comp. Appl. Math., 162(2):299--326, 2004.

Digital Library

[11]

I. M. Gel'fand and A. A. Kirillov. Sur les corps Liés aux algèbres enveloppantes des algèbres de Lie. Publications Mathématiques de l'IHÉS, 31:5--19, 1966.

[12]

D. Grigor'ev. Complexity of factoring and calculating the GCD of linear ordinary differential operators. J. Symb. Comput., 10(1):7--37, 1990.

Digital Library

[13]

D. Grigoriev and F. Schwarz. Factoring and solving linear partial differential equations. Computing, 73(2):179--197, 2004.

Digital Library

[14]

A. Heinle and V. Levandovskyy. Factorization of polynomials in Z-graded skew polynomial rings. ACM Commun. Comput. Algebra, 44(3/4):113--114, 2011.

Digital Library

[15]

A. Heinle and V. Levandovskyy. Factorization of Z-homogeneous polynomials in the first (q)--Weyl algebra. arXiv preprint arXiv:1302.5674, 2013.

[16]

A. Heinle, V. Levandovskyy, and A. Nareike. Symbolicdata: SDeval --- benchmarking for everyone. arXiv preprint arXiv:1310.5551, 2013.

[17]

M. Kashiwara. Vanishing cycle sheaves and holonomic systems of differential equations. In Algebraic Geometry, pages 134--142. Springer, 1983.

[18]

W. Koepf. Hypergeometric summation. An algorithmic approach to summation and special function identities. Wiesbaden: Vieweg, 1998.

[19]

E. Landau. Ein Satz über die Zerlegung homogener linearer Differentialausdrücke in irreductible Factoren. Journal für die reine und angewandte Mathematik, 124:115--120, 1902.

[20]

A. Loewy. Über reduzible lineare homogene Differentialgleichungen. Math. Ann., 56:549--584, 1903.

[21]

A. Loewy. Über vollständig reduzible lineare homogene Differentialgleichungen. Math. Ann., 62:89--117, 1906.

[22]

B. Malgrange. Polynômes de Bernstein-Sato et cohomologie evanescente. Astérisque, 101-102:243--267, 1983.

[23]

H. Melenk and J. Apel. REDUCE package NCPOLY: Computation in non-commutative polynomial ideals. Konrad-Zuse-Zentrum Berlin (ZIB), 1994.

[24]

M. B. Monagan, K. O. Geddes, K. M. Heal, G. Labahn, S. M. Vorkoetter, J. McCarron, and P. DeMarco. Maple Introductory Programming Guide. Maplesoft, 2008.

[25]

M. Saito, B. Sturmfels, and N. Takayama. Gröbner deformations of hypergeometric differential equations. Berlin: Springer, 2000.

Digital Library

[26]

F. Schwarz. A factorization algorithm for linear ordinary differential equations. In Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, pages 17--25. ACM, 1989.

Digital Library

[27]

F. Schwarz. Alltypes in the web. ACM Commun. Comput. Algebra, 42(3):185--187, Feb. 2009.

Digital Library

[28]

E. Shemyakova. Parametric factorizations of second-, third- and fourth-order linear partial differential operators with a completely factorable symbol on the plane. Mathematics in Computer Science, 1(2):225--237, 2007.

[29]

E. Shemyakova. Multiple factorizations of bivariate linear partial differential operators. In Proc. CASC 2009, pages 299--309. Springer, 2009.

Digital Library

[30]

E. Shemyakova. Refinement of two-factor factorizations of a linear partial differential operator of arbitrary order and dimension. Mathematics in Computer Science, 4:223--230, 2010. 10.1007/s11786-010-0052-3.

[31]

S. Tsarev. Problems that appear during factorization of ordinary linear differential operators. Program. Comput. Softw., 20(1):27--29, 1994.

[32]

S. Tsarev. An algorithm for complete enumeration of all factorizations of a linear ordinary differential operator. In Proc. ISSAC 1996. New York, NY: ACM Press, 1996.

Digital Library

[33]

M. van Hoeij. Factorization of linear differential operators. PhD thesis, University of Nijmegen, 1996.

[34]

M. van Hoeij. Factorization of differential operators with rational functions coefficients. J. Symb. Comput., 24(5):537--561, 1997.

Digital Library

[35]

M. van Hoeij. Formal solutions and factorization of differential operators with power series coefficients. J. Symb. Comput., 24(1):1--30, 1997.

Digital Library

[36]

M. van Hoeij and Q. Yuan. Finding all Bessel type solutions for linear differential equations with rational function coefficients. In Proc. ISSAC 2010, pages 37--44. ACM Press, 2010.

Digital Library

Cited By

Heinle ALevandovskyy VAbramov SZima EGao X(2016)A Factorization Algorithm for G-Algebras and ApplicationsProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930906(263-270)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930906
Heinle ALevandovskyy V(2015)The SDEval benchmarking toolkitACM Communications in Computer Algebra10.1145/2768577.276857849:1(1-9)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1145/2768577.2768578

Index Terms

Factoring linear differential operators in n variables
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical software

Recommendations

Factoring linear partial differential operators in n variables

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial nth Weyl algebra, the polynomial nth shift algebra, and Z n -graded polynomials in the nth q _ -Weyl algebra.The most unexpected result ...
A Constructive Study of the Module Structure of Rings of Partial Differential Operators

The purpose of this paper is to develop constructive versions of Stafford's theorems on the module structure of Weyl algebras A _n(k) (i.e., the rings of partial differential operators with polynomial coefficients) over a base field k of characteristic ...
Factoring the characteristic polynomial of a lattice

We introduce a new method for showing that the roots of the characteristic polynomial of certain finite lattices are all nonnegative integers. This method is based on the notion of a quotient of a poset which will be developed to explain this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

July 2014

444 pages

ISBN:9781450325011

DOI:10.1145/2608628

Editor:
Katsusuke Nabeshima
The University of Tokushima, Japan
,
General Chairs:
Kosaku Nagasaka
Kobe University, Japan
,
Franz Winkler
RISC, University Linz, Austria
,
Program Chair:
Agnes Szanto
North Carolina State University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSAC '14

ISSAC '14: International Symposium on Symbolic and Algebraic Computation

July 23 - 25, 2014

Kobe, Japan

Acceptance Rates

ISSAC '14 Paper Acceptance Rate 51 of 96 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Heinle ALevandovskyy VAbramov SZima EGao X(2016)A Factorization Algorithm for G-Algebras and ApplicationsProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930906(263-270)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930906
Heinle ALevandovskyy V(2015)The SDEval benchmarking toolkitACM Communications in Computer Algebra10.1145/2768577.276857849:1(1-9)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1145/2768577.2768578

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents