Article

Homotopy methods for equations over finite fields

Author:

AAECC'03: Proceedings of the 15th international conference on Applied algebra, algebraic algorithms and error-correcting codes

Pages 18 - 23

Published: 12 May 2003 Publication History

Abstract

This paper describes an application of some ideas from homotopy theory to the problem of computing the number of solutions to a multivariate polynomial equation over a finite field. The benefit of the homotopy approach over more direct methods is that the running-time is far less dependent on the number of variables. The method was introduced by the author in another paper, where specific complexity estimates were obtained for certain special cases. Some consequences of these estimates are stated in the present paper.

References

[1]

J.-P. Dedieu, Newton's method and some complexity aspects of the zero-finding problem, in "Foundations of Computational Mathematics", (R.A. DeVore, A. Iserles, E. Suli), LMS Lecture Note Series 284, Cambridge University Press, 2001, 45-67.

Google Scholar

[2]

B. Dwork, On the zeta function of a hypersurface II, Ann. Math. (2) 80, (1964), 227-299.

Crossref

Google Scholar

[3]

J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, 1999.

Digital Library

Google Scholar

[4]

N.M. Katz, On the differential equations satisfied by period matrices, Pub. Math. IHES 35, (1968), 71-106.

Crossref

Google Scholar

[5]

K. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, Journal of the Ramanujan Mathematical Society, 16 (2001), 323-338.

Google Scholar

[6]

A.G.B. Lauder, Deformation theory and the computation of zeta functions, submitted. Preprint available at: http://web.comlab.ox.ac.uk/oucl/work/alan.lauder/

Google Scholar

[7]

A.G.B. Lauder and D. Wan, Counting points on varieties over finite fields of small characteristic, to appear in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (Mathematical Sciences Research Institute Publications), J.P. Buhler and P. Stevenhagen (eds), Cambridge University Press.

Google Scholar

Recommendations

A general approach to hyperbolic partial differential equations by homotopy perturbation method

The hyperbolic partial differential equations (PDEs) have a wide range of applications in science and engineering. In this article, the exact solutions of some hyperbolic PDEs are presented by means of He's homotopy perturbation method (HPM). The ...
He's homotopy perturbation method for fourth-order parabolic equations

In this paper, He's homotopy perturbation method is applied to fourth-order parabolic partial differential equations with variable coefficients to obtain the analytic solution. The method is tested on six examples, which reveal its effectiveness and ...
Some notes on using the homotopy perturbation method for solving time-dependent differential equations

Although attempts have been made to solve time-dependent differential equations using homotopy perturbation method (HPM), none of the researchers have provided a universal homotopy equation. In this paper, going one step forward, we intend to make some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAECC'03: Proceedings of the 15th international conference on Applied algebra, algebraic algorithms and error-correcting codes

May 2003

265 pages

ISBN:3540401113

Editors:
Marc Fossorier
University of Hawaii, Department of Electrical Engineering, Honolulu, HI
,
Tom Høholdt
The Technical University of Denmark, Department of Mathematics, Lyngby, Denmark
,
Alain Poli
IRIT, Université Paul Sabatier, Toulouse cédex, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 May 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

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

Abstract

References

Recommendations

A general approach to hyperbolic partial differential equations by homotopy perturbation method

He's homotopy perturbation method for fourth-order parabolic equations

Some notes on using the homotopy perturbation method for solving time-dependent differential equations

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations