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

research-article

Change of Basis for m-primary Ideals in One and Two Variables

Authors:

Seung Gyu Hyun,

Stephen Melczer,

Catherine St-PierreAuthors Info & Claims

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

Pages 227 - 234

https://doi.org/10.1145/3326229.3326268

Published: 08 July 2019 Publication History

Abstract

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear mappings, called untangling and \emphtangling by those authors, that arise in the context of computations with univariate polynomials. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings, and use them to give bounds on the arithmetic complexity of certain algebras.

References

[1]

A. V. Aho, K. Steiglitz, and J. D. Ullman. 1975. Evaluating polynomials at fixed sets of points. SIAM J. Comp., Vol. 4, 4 (1975), 533--539.

Digital Library

[2]

M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. 1996. Zeroes, multiplicities and idempotents for zerodimensional systems. In MEGA'94 . Birkh"auser, 1--15.

[3]

P. Aubry, D. Lazard, and M. Moreno Maza. 1999. On the theories of triangular sets. J. Symb. Comput.C, Vol. 28, 1,2 (1999), 45--124.

[4]

J. Berthomieu, B. Boyer, and J.-C. Faugè re. 2017. Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences. J. Symb. Comput., Vol. 83 (2017), 36--67.

[5]

A. Bostan, X. Caruso, G. Christol, and P. Dumas. 2018. Fast coefficient computation for algebraic power series in positive characteristic. In ANTS-XIII . Mathematical Sciences Publishers.

[6]

A. Bostan, C. Jeannerod, C. Mouilleron, and É. Schost. 2017. On matrices with displacement structure: generalized operators and faster algorithms. SIAM J. Matrix Anal. Appl., Vol. 38, 3 (2017), 733--775.

Digital Library

[7]

A. Bostan, G. Lecerf, and É. Schost. 2003. Tellegen's principle into practice. In ISSAC'03. ACM, 37--44.

Digital Library

[8]

R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun. 1980. Fast solution of Toeplitz systems of equations and computation of Padé approximants. J. of Algorithms, Vol. 1, 3 (1980), 259--295.

[9]

J. Canny. 1990. Generalised characteristic polynomials. J. Symb. Comput., Vol. 9 (1990), 241--250.

Digital Library

[10]

J. Canny, E. Kaltofen, and Y. Lakshman. 1989. Solving systems of non-linear polynomial equations faster. In ISSAC'89. ACM, 121--128.

Digital Library

[11]

M. F. I. Chowdhury, C.-P. Jeannerod, V. Neiger, É. Schost, and G. Villard. 2015. Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations. IEEE Transactions on Information Theory, Vol. 61, 5 (2015), 2370--2387.

Digital Library

[12]

D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput., Vol. 9, 3 (1990), 251--280.

Digital Library

[13]

X. Dahan. 2017. GCD modulo a primary triangular set of dimension zero. In ISSAC'17. ACM, 109--116.

Digital Library

[14]

L. De Feo and É. Schost. 2012. Fast arithmetics in Artin-Schreier towers over finite fields. J. Symb. Comput., Vol. 47, 7 (2012), 771--792.

Digital Library

[15]

D. Eisenbud. 1996. Commutative Algebra with a view toward Algebraic Geometry . Number 150 in GTM. Springer.

[16]

C. M. Fiduccia. 1985. An efficient formula for linear recurrences. SIAM J. Comput., Vol. 14, 1 (1985), 106--112.

Digital Library

[17]

J. Gathen and J. Gerhard. 2013. Modern Computer Algebra third ed.). Cambridge University Press, Cambridge.

Digital Library

[18]

J. von zur Gathen and V. Shoup. 1992. Computing Frobenius maps and factoring polynomials. Computational Complexity, Vol. 2, 3 (1992), 187--224.

[19]

M. Giesbrecht. 1995. Nearly optimal algorithms for canonical matrix forms. SIAM J. Comput., Vol. 24, 5 (1995), 948--969.

Digital Library

[20]

M. Giusti and J. Heintz. 1993. La détermination des points isolés et de la dimension d'une variété peut se faire en temps polynomial. In Computational algebraic geometry and commutative algebra, Vol. XXXIV. 216--256.

[21]

J. D. Hauenstein, B. Mourrain, and A. Szanto. 2017. On deflation and multiplicity structure. J. Symb. Comput., Vol. 83 (2017), 228--253.

[22]

J. van der Hoeven and G. Lecerf. 2017. Composition modulo powers of polynomials. In ISSAC'17. ACM, 445--452.

Digital Library

[23]

M. Kaminski, D.G. Kirkpatrick, and N.H. Bshouty. 1988. Addition requirements for matrix and transposed matrix products. J. Algorithms, Vol. 9, 3 (1988), 354--364.

Digital Library

[24]

D. Lazard. 1985. Ideal bases and primary decomposition: case of two variables. J. Symbolic Comput., Vol. 1, 3 (1985), 261--270.

Digital Library

[25]

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

Digital Library

[26]

R. Lebreton, E. Mehrabi, and É. Schost. 2013. On the complexity of solving bivariate systems: the case of non-singular solutions. In ISSAC'13 . ACM, 251--258.

Digital Library

[27]

F. S. Macaulay. 1916. The Algebraic Theory of Modular Systems .Cambridge University Press.

[28]

M. G. Marinari, H. M. Möller, and T. Mora. 1996. On multiplicities in polynomial system solving. Trans. Amer. Math. Soc., Vol. 348, 8 (1996), 3283--3321.

[29]

E. Mehrabi and É . Schost. 2016. A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers. J. Complexity, Vol. 34 (2016), 78--128.

Digital Library

[30]

V. Neiger, H. Rahkooy, and É. Schost. 2017. Algorithms for zero-dimensional ideals using linear recurrent sequences. In CASC'17 . Springer, 313--328.

[31]

A. Ranum. 1911. The general term of a recurring series. Bull. Amer. Math. Soc., Vol. 17, 9 (1911), 457--461.

[32]

F. Rouillier. 1999. Solving zero-dimensional systems through the Rational Univariate Representation. AAECC, Vol. 9, 5 (1999), 433--461.

[33]

V. Shoup. 1994. Fast construction of irreducible polynomials over finite fields. J. Symb. Comput., Vol. 17, 5 (1994), 371--391.

Digital Library

[34]

V. Shoup. 1999. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In ISSAC'99. ACM, 53--58.

Digital Library

[35]

Joris Van Der Hoeven and Robin Larrieu. 2018. Fast reduction of bivariate polynomials with respect to sufficiently regular Gröbner bases. (2018).

[36]

W. T. Wu. 1986. On zeros of algebraic equations -- an application of Ritt principle. Kexue Tongbao, Vol. 31 (1986), 1--5.

Cited By

Schost ÉSt-Pierre C(2024) An -adic algorithm for bivariate Gröbner bases Journal of Symbolic Computation10.1016/j.jsc.2024.102389(102389)Online publication date: Sep-2024
https://doi.org/10.1016/j.jsc.2024.102389
Villard G(2024)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367(102367)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2024.102367
Schost ÉSt-Pierre C(2023)p-adic algorithm for bivariate Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597086(508-516)Online publication date: 24-Jul-2023
https://doi.org/10.1145/3597066.3597086

Index Terms

Change of Basis for m-primary Ideals in One and Two Variables
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Hahn, Jacobi, and Krawtchouk polynomials of several variables

Hahn polynomials of several variables can be defined by using the Jacobi polynomials on the simplex as a generating function. Starting from this connection, a number of properties for these two families of orthogonal polynomials are derived. It is shown ...
On a Hermite Interpolation by Polynomials of Two Variables

A problem of Hermite interpolation by polynomials of two variables is studied. The interpolation matches preassigned data of function values and consecutive normal derivatives on a set of points on several circles centered at the origin. It includes ...
Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity

Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Grobner bases algorithms seems to be easier than solving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

July 2019

418 pages

ISBN:9781450360845

DOI:10.1145/3326229

General Chairs:
James Davenport
University of Bath, UK
,
Dongming Wang
Beihang University, China; Guangxi University for Nationalities, China; Centre National de la Recherche Scientifique, France
,
Program Chair:
Manuel Kauers
Johannes Kepler University, Austria
,
Publications Chair:
Russell Bradford
University of Bath, UK

Copyright © 2019 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2019

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 '19

ISSAC '19: International Symposium on Symbolic and Algebraic Computation

July 15 - 18, 2019

Beijing, China

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
68
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schost ÉSt-Pierre C(2024) An -adic algorithm for bivariate Gröbner bases Journal of Symbolic Computation10.1016/j.jsc.2024.102389(102389)Online publication date: Sep-2024
https://doi.org/10.1016/j.jsc.2024.102389
Villard G(2024)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367(102367)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2024.102367
Schost ÉSt-Pierre C(2023)p-adic algorithm for bivariate Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597086(508-516)Online publication date: 24-Jul-2023
https://doi.org/10.1145/3597066.3597086
Dahan X(2023)Chinese Remainder Theorem for bivariate lexicographic Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597082(208-217)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597082

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.

Figures

Tables

Media

View Table of Conten