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

research-article

Computation of the Similarity Class of the p-Curvature

Authors:

Éric SchostAuthors Info & Claims

ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

Pages 111 - 118

https://doi.org/10.1145/2930889.2930897

Published: 20 July 2016 Publication History

Abstract

The p-curvature of a system of linear differential equations in positive characteristic p is a matrix that measures how far the system is from having a basis of polynomial solutions. We show that the similarity class of the p-curvature can be determined without computing the p-curvature itself. More precisely, we design an algorithm that computes the invariant factors of the p-curvature in time quasi-linear in √ p. This is much less than the size of the p-curvature, which is generally linear in p. The new algorithm allows to answer a question originating from the study of the Ising model in statistical physics.

References

[1]

Y. André. Sur la conjecture des p-courbures de Grothendieck-Katz et un problème de Dwork. In Geometric aspects of Dwork theory. Vol. I, II, pages 55--112. Walter de Gruyter GmbH & Co. KG, Berlin, 2004.

[2]

A. Bostan, S. Boukraa, S. Hassani, J.-M. Maillard, J.-A. Weil, and N. Zenine. Globally nilpotent differential operators and the square Ising model. J. Phys. A, 42(12):125206, 50, 2009.

[3]

A. Bostan, X. Caruso, and E. Schost. A fast algorithm for computing the characteristic polynomial of the p-curvature. In ISSAC'14, pages 59--66. ACM, New York, 2014.

Digital Library

[4]

A. Bostan, X. Caruso, and E. Schost. A fast algorithm for computing the p-curvature. In ISSAC'15, pages 69--76. ACM, New York, 2015.

Digital Library

[5]

A. Bostan, T. Cluzeau, and B. Salvy. Fast algorithms for polynomial solutions of linear differential equations. In ISSAC'05, pages 45--52. ACM Press, 2005.

Digital Library

[6]

A. Bostan, P. Gaudry, and É. Schost. Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM Journal on Computing, 36(6):1777--1806, 2007.

Digital Library

[7]

A. Bostan and M. Kauers. Automatic classification of restricted lattice walks. In FPSAC'09, DMTCS Proc., AK, pages 201--215. 2009.

[8]

A. Bostan and M. Kauers. The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc., 138(9):3063--3078, 2010. With an appendix by Mark van Hoeij.

[9]

A. Bostan and É. Schost. Fast algorithms for differential equations in positive characteristic. In ISSAC'09, pages 47--54. ACM, New York, 2009.

Digital Library

[10]

S. Boukraa, S. Hassani, I. Jensen, J.-M. Maillard, and N. Zenine. High-order Fuchsian equations for the square lattice Ising model: Χ(6). J. Phys. A, 43(11):115201, 22, 2010.

[11]

D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inform., 28(7):693--701, 1991.

Digital Library

[12]

D. V. Chudnovsky and G. V. Chudnovsky. Approximations and complex multiplication according to Ramanujan. In Ramanujan revisited (Urbana-Champaign, 1987), pages 375--472. Academic Press, Boston, 1988.

[13]

T. Cluzeau. Factorization of differential systems in characteristic p. In ISSAC'03, pages 58--65. ACM Press, 2003.

Digital Library

[14]

W. Eberly. Asymptotically efficient algorithms for the Frobenius form. Technical report, 2000.

[15]

F. L. Gall. Powers of tensors and fast matrix multiplication. In ISSAC'14, pages 296--303, 2014.

Digital Library

[16]

F. R. Gantmacher. The theory of matrices. Vols. 1, 2. Translated by K. A. Hirsch. Chelsea Publishing Co., New York, 1959.

[17]

J.gathenvon zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, second edition, 2003.

Digital Library

[18]

M. Giesbrecht. Nearly optimal algorithms for canonical matrix forms. PhD thesis, University of Toronto, 1993.

Digital Library

[19]

M. Giesbrecht. Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24(5):948--969, 10 1995.

Digital Library

[20]

M. Giesbrecht and A. Storjohann. Computing rational forms of integer matrices. Journal of Symbolic Computation, 34(3):157--172, 2002.

Digital Library

[21]

D. Harvey, J. van der Hoeven, and G. Lecerf. Faster polynomial multiplication over finite fields. http://arxiv.org/abs/1407.3361, 2014.

[22]

T. Honda. Algebraic differential equations. In Symposia Mathematica, Vol. XXIV, pages 169--204. Academic Press, London, 1981.

[23]

E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders. Fast parallel computation of Hermite and Smith forms of polynomial matrices. SIAM Journal on Matrix Analysis and Applications, 8(4):683--690, 1987.

Digital Library

[24]

E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications, 136:189--208, 1990.

[25]

E. Kaltofen and G. Villard. On the complexity of computing determinants. Comput. Complexity, 13(3--4):91--130, 2004.

Digital Library

[26]

N. M. Katz. Algebraic solutions of differential equations (p-curvature and the Hodge filtration). Invent. Math., 18:1--118, 1972.

[27]

N. M. Katz. A conjecture in the arithmetic theory of differential equations. Bull. Soc. Math. France, (110):203--239, 1982.

[28]

C. Pernet and A. Storjohann. Frobenius form in expected matrix multiplication time over sufficiently large fields, 2007.

[29]

A. Schönhage. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Informatica, 7:395--398, 1977.

Digital Library

[30]

A. Storjohann. Deterministic computation of the Frobenius form. In FOCS'01, pages 368--377. IEEE Computer Society Press, 2001.

Digital Library

[31]

A. Storjohann and G. Labahn. A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix. Linear Algebra and its Applications, 253(1-3):155--173, 1997.

[32]

M. van der Put. Differential equations in characteristic p. Compositio Mathematica, 97:227--251, 1995.

[33]

M. van der Put. Reduction modulo p of differential equations. Indag. Mathem., 7(3):367--387, 1996.

Cited By

Bostan ACaruso XRoques J(2024)Algebraic solutions of linear differential equations: An arithmetic approachBulletin of the American Mathematical Society10.1090/bull/183561:4(609-658)Online publication date: 15-Aug-2024
https://doi.org/10.1090/bull/1835
Kauers MKoutschan CMaza MZhi L(2022)Guessing with Little DataProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535486(83-90)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535486
Di Vizio LHardouin CGranier A(2022)Intrinsic Approach to Galois Theory of 𝑞-Difference EquationsMemoirs of the American Mathematical Society10.1090/memo/1376279:1376Online publication date: Sep-2022
https://doi.org/10.1090/memo/1376
Show More Cited By

Index Terms

Computation of the Similarity Class of the p-Curvature
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

A fast algorithm for computing the characteristic polynomial of the p-curvature
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

We discuss theoretical and algorithmic questions related to the p-curvature of differential operators in characteristic p. Given such an operator L, and denoting by Ξ(L) the characteristic polynomial of its p-curvature, we first prove a new, alternative,...
Fast algorithms for differential equations in positive characteristic
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

We address complexity issues for linear differential equations in characteristic p >;0: resolution and computation of the p-curvature. For these tasks, our main focus is on algorithms whose complexity behaves well with respect to p. We prove bounds ...
A Fast Algorithm for Computing the P-curvature
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

We design an algorithm for computing the p-curvature of a differential system in positive characteristic p. For a system of dimension r with coefficients of degree at most d, its complexity is O~ (p d r^ω) operations in the ground field (where ω denotes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

July 2016

434 pages

ISBN:9781450343800

DOI:10.1145/2930889

General Chairs:
Sergei Abramov
Russian Academy of Sciences, Russia
,
Eugene Zima
Wilfrid Laurier University, Canada
,
Program Chair:
Xiao-Shan Gao
Chinese Academy of Sciences, China

Copyright © 2016 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Sciences and Engineering Research Council of Canada

Conference

ISSAC '16

Sponsor:

SIGSAM

ISSAC '16: International Symposium on Symbolic and Algebraic Computation

July 20 - 22, 2016

ON, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
46
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bostan ACaruso XRoques J(2024)Algebraic solutions of linear differential equations: An arithmetic approachBulletin of the American Mathematical Society10.1090/bull/183561:4(609-658)Online publication date: 15-Aug-2024
https://doi.org/10.1090/bull/1835
Kauers MKoutschan CMaza MZhi L(2022)Guessing with Little DataProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535486(83-90)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535486
Di Vizio LHardouin CGranier A(2022)Intrinsic Approach to Galois Theory of 𝑞-Difference EquationsMemoirs of the American Mathematical Society10.1090/memo/1376279:1376Online publication date: Sep-2022
https://doi.org/10.1090/memo/1376
Pagès RChyzak FLabahn G(2021)Computing Characteristic Polynomials of p-Curvatures in Average Polynomial TimeProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465524(329-336)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465524
Bostan AEmiris IZhi LMantzaflaris A(2020)Computing the N-th term of a q-holonomic sequenceProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404060(46-53)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404060

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