Computer Algebra for Geometry

Algebraic varieties are defined by polynomial equations. Computer algebra methods for solving systems of polynomial equations and similar problems form the basis for a computational theory of Algebraic Geometry.

From the preface of J. R. Sendra, F. Winkler, S. Pérez-Díaz. Rational Algebraic Curves - A Computer Algebra Approach, Springer-Verlag Berlin Heidelberg, 2008.

Algebraic curves and surfaces are an old topic of geometric and algebraic investigation. They have found applications for instance in ancient and modern architectural designs, in number theoretic problems, in models of biological shapes, in error-correcting codes, and in cryptographic algorithms. Recently they have gained additional practical importance as central objects in computer aided geometric design. Modern airplanes, cars, and household appliances would be unthinkable without the computational manipulation of algebraic curves and surfaces. Algebraic curves and surfaces combine
fascinating mathematical beauty with challenging computational complexity and wide spread practical applicability.

In this book we treat only algebraic curves, although many of the results and methods can be and in fact have been generalized to surfaces. Being the solution loci of algebraic, i.e. polynomial,
equations in two variables, plane algebraic curves are well suited for being investigated with symbolic computer algebra methods. This is exactly the approach we take in our book. We apply algorithms from computer algebra to the analysis, and manipulation of algebraic curves. To a large extent this amounts to being able to represent these algebraic curves in different ways, such as implicitly by defining polynomials, parametrically by rational functions, or locally parametrically by power series expansions around a point. These representations all have their individual advantages; an implicit representation lets us decide easily whether a given point actually lies on a given curve, a parametric representation allows us to generate points of a given curve over the desired coordinate fields, and with the help of a power series expansion we can for instance overcome the numerical problems of tracing a curve through a singularity.

The central problem in this book is the determination of rational parametrizability of a curve, and, in case it exists, the computation of a good rational parametrization. This amounts to determining the genus of a curve, i.e. its complete singularity structure, computing regular points of the curve in small coordinate fields, and constructing linear systems of curves with prescribed intersection multiplicities. Various optimality criteria for rational parametrizations of algebraic curves are discussed. We also point to some applications of these techniques in computer aided geometric design. Many of the symbolic algorithmic methods described in our book are implemented in the program system CASA, which is based on the computer algebra system Maple.

Our book is mainly intended for graduate students specializing in constructive algebraic curve geometry. We hope that researchers wanting to get a quick overview of what can be done with algebraic curves in terms of symbolic algebraic computation will also find this book helpful.

Members

Loading…

Ongoing Projects

Software

Publications

2018

Rational General Solutions of Systems of First-Order Partial Differential Equations

Georg Grasegger, Alberto Lastra, J. Rafael Sendra, Franz Winkler

Journal of Computational and Applied Mathematics 331, pp. 88-103. 2018. ISSN: 0377-0427.
[bib]
@article{RISC5509,
author = {Georg Grasegger and Alberto Lastra and J. Rafael Sendra and Franz Winkler},
title = {{Rational General Solutions of Systems of First-Order Partial Differential Equations}},
language = {english},
journal = {Journal of Computational and Applied Mathematics},
volume = {331},
pages = {88--103},
isbn_issn = {ISSN: 0377-0427},
year = {2018},
refereed = {yes},
length = {16}
}

Deciding the Existence of Rational General Solutions for First-Order Algebraic ODEs

N.T. Vo, G. Grasegger, F. Winkler

Journal of Symbolic Computation 87, pp. 127-139. 2018. ISSN 0747-7171.
[bib]
@article{RISC5589,
author = {N.T. Vo and G. Grasegger and F. Winkler},
title = {{Deciding the Existence of Rational General Solutions for First-Order Algebraic ODEs}},
language = {english},
journal = {Journal of Symbolic Computation},
volume = {87},
pages = {127--139},
isbn_issn = {ISSN 0747-7171},
year = {2018},
refereed = {yes},
length = {12}
}

A Computable Extension for Holonomic Functions: DD-Finite Functions

Jiménez-Pastor Antonio, Pillwein Veronika

Journal of Symbolic Computation, pp. -. 2018. ISSN 0747-7171. accepted.
[bib]
@article{RISC5731,
author = {Jiménez-Pastor Antonio and Pillwein Veronika},
title = {{A Computable Extension for Holonomic Functions: DD-Finite Functions}},
language = {english},
journal = {Journal of Symbolic Computation},
pages = {--},
isbn_issn = {ISSN 0747-7171},
year = {2018},
note = {accepted},
refereed = {yes},
length = {0}
}

The Number of Realizations of a Laman Graph

Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, Josef Schicho

SIAM Journal on Applied Algebra and Geometry 2(1), pp. 94-125. 2018. 2470-6566. [url]
[bib]
@article{RISC5700,
author = {Jose Capco and Matteo Gallet and Georg Grasegger and Christoph Koutschan and Niels Lubbes and Josef Schicho},
title = {{The Number of Realizations of a Laman Graph}},
language = {english},
journal = {SIAM Journal on Applied Algebra and Geometry},
volume = {2},
number = {1},
pages = {94--125},
isbn_issn = {2470-6566},
year = {2018},
refereed = {yes},
length = {32},
url = {https://doi.org/10.1137/17M1118312}
}

Representing (q-)hypergeometric products and mixed versions in difference rings

E.D. Ocansey, C. Schneider

In: Advances in Computer Algebra. WWCA 2016., C. Schneider, E. Zima (ed.), Springer Proceedings in Mathematics & Statistics 226, pp. 175-213. 2018. Springer, ISSN 2194-1009. arXiv:1705.01368 [cs.SC]. [url]
[bib]
@incollection{RISC5448,
author = {E.D. Ocansey and C. Schneider},
title = {{Representing (q-)hypergeometric products and mixed versions in difference rings}},
booktitle = {{ Advances in Computer Algebra. WWCA 2016.}},
language = {english},
series = {Springer Proceedings in Mathematics & Statistics},
volume = {226},
pages = {175--213},
publisher = {Springer},
isbn_issn = {ISSN 2194-1009},
year = {2018},
note = {arXiv:1705.01368 [cs.SC]},
editor = {C. Schneider and E. Zima},
refereed = {yes},
length = {36},
url = {https://arxiv.org/abs/1705.01368}
}

2017

Relative Reduction and Buchberger’s Algorithm in Filtered Free Modules

Christoph Fuerst, Alexander Levin

In: Mathematics in Computer Science, W. Koepf (ed.), pp. 1-11. 2017. 1661-8289.
[bib]
@inproceedings{RISC5432,
author = {Christoph Fuerst and Alexander Levin},
title = {{Relative Reduction and Buchberger’s Algorithm in Filtered Free Modules}},
booktitle = {{Mathematics in Computer Science}},
language = {english},
pages = {1--11},
isbn_issn = {1661-8289},
year = {2017},
editor = {W. Koepf},
refereed = {yes},
length = {11}
}

An Algebraic-Geometric Method for Computing Zolotarev Polynomials

Georg Grasegger, N. Thieu Vo

In: Proceedings of the 2017 international symposium on symbolic and algebraic computation (ISSAC), Burr, M. (ed.), pp. 173-180. 2017. ACM Press, New York, ISBN: 978-1-4503-5064-8.
[bib]
@inproceedings{RISC5510,
author = {Georg Grasegger and N. Thieu Vo},
title = {{An Algebraic-Geometric Method for Computing Zolotarev Polynomials}},
booktitle = {{Proceedings of the 2017 international symposium on symbolic and algebraic computation (ISSAC)}},
language = {english},
pages = {173--180},
publisher = {ACM Press},
address = {New York},
isbn_issn = {ISBN: 978-1-4503-5064-8},
year = {2017},
editor = {Burr and M.},
refereed = {yes},
length = {8}
}

Computing the number of realizations of a Laman graph

Jose Capco, Georg Grasegger, Matteo Gallet, Christoph Koutschan, Niels Lubbes, Josef Schicho

In: Electronic Notes in Discrete Mathematics (Proceedings of Eurocomb 2017), Vadim Lozin (ed.), Proceedings of The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17)61, pp. 207-213. 2017. ISSN 1571-0653. [url]
[bib]
@inproceedings{RISC5478,
author = {Jose Capco and Georg Grasegger and Matteo Gallet and Christoph Koutschan and Niels Lubbes and Josef Schicho},
title = {{Computing the number of realizations of a Laman graph}},
booktitle = {{Electronic Notes in Discrete Mathematics (Proceedings of Eurocomb 2017)}},
language = {english},
abstract = {Laman graphs model planar frameworks which are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. In a recent paper we provide a recursion formula for this number of realizations using ideas from algebraic and tropical geometry. Here, we present a concise summary of this result focusing on the main ideas and the combinatorial point of view.},
volume = {61},
pages = {207--213},
isbn_issn = {ISSN 1571-0653},
year = {2017},
editor = {Vadim Lozin},
refereed = {yes},
keywords = {Laman graph; minimally rigid graph; tropical geometry; euclidean embedding; graph realization},
length = {7},
conferencename = {The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17)},
url = {http://www.koutschan.de/data/laman/}
}

2016

Axiomatic Description of Gröbner Reduction

Christoph Fuerst

RISC, JKU Linz. PhD Thesis. December 2016. [pdf]
[bib]
@phdthesis{RISC5388,
author = {Christoph Fuerst},
title = {{Axiomatic Description of Gröbner Reduction}},
language = {english},
year = {2016},
month = {December},
translation = {0},
school = {RISC, JKU Linz},
length = {154}
}

A solution method for autonomous first-order algebraic partial differential equations

G. Grasegger, A. Lastra, J.R. Sendra, F. Winkler

Journal of Computational and Applied Mathematics 300, pp. 119-133. 2016. 0377-0427. [url]
[bib]
@article{RISC5202,
author = {G. Grasegger and A. Lastra and J.R. Sendra and F. Winkler},
title = {{A solution method for autonomous first-order algebraic partial differential equations}},
language = {english},
journal = {Journal of Computational and Applied Mathematics},
volume = {300},
pages = {119--133},
isbn_issn = {0377-0427},
year = {2016},
refereed = {yes},
length = {15},
url = {http://dx.doi.org/10.1016/j.cam.2015.12.030}
}

A decision algorithm for rational general solutions of first-order algebraic ODEs

G. Grasegger, N.T. Vo, F. Winkler

In: Proceedings XV Encuentro de Algebra Computacional y Aplicaciones (EACA 2016), Universidad de la Rioja, J. Heras and A. Romero (eds.) (ed.), pp. 101-104. 2016. 978-84-608-9024-9.
[bib]
@inproceedings{RISC5400,
author = {G. Grasegger and N.T. Vo and F. Winkler},
title = {{A decision algorithm for rational general solutions of first-order algebraic ODEs}},
booktitle = {{Proceedings XV Encuentro de Algebra Computacional y Aplicaciones (EACA 2016)}},
language = {english},
pages = {101--104},
isbn_issn = {978-84-608-9024-9},
year = {2016},
editor = {Universidad de la Rioja and J. Heras and A. Romero (eds.)},
refereed = {yes},
length = {4}
}

Inverse Inequality Estimates with Symbolic Computation

Christoph Koutschan and Martin Neumüller and Cristian-Silviu Radu

Advances in Applied Mathematics, pp. 1-23. 2016. 0196-8858. [pdf]
[bib]
@article{RISC5454,
author = {Christoph Koutschan and Martin Neumüller and Cristian-Silviu Radu},
title = {{Inverse Inequality Estimates with Symbolic Computation}},
language = {english},
journal = {Advances in Applied Mathematics},
pages = {1--23},
isbn_issn = {0196-8858},
year = {2016},
refereed = {yes},
length = {23}
}

Representation of hypergeometric products in difference rings

E.D. Ocansey, C. Schneider

ACM Communications in Computer Algebra 50(4), pp. 161-163. 2016. ISSN 1932-2240 . Extended abstract of the poster presentation at ISSAC 2016. [pdf]
[bib]
@article{RISC5316,
author = {E.D. Ocansey and C. Schneider},
title = {{Representation of hypergeometric products in difference rings}},
language = {english},
journal = {ACM Communications in Computer Algebra},
volume = {50},
number = {4},
pages = {161--163},
isbn_issn = {ISSN 1932-2240 },
year = {2016},
note = {Extended abstract of the poster presentation at ISSAC 2016},
refereed = {yes},
length = {3}
}

Denominator Bounds for Higher Order Systems of Linear Recurrence Equations

J. Middeke, C. Schneider

ACM Communications in Computer Algebra 50(4), pp. 185-187. 2016. ISSN 1932-2240. Extended abstract of the poster presentation at ISSAC 2016. [pdf]
[bib]
@article{RISC5317,
author = {J. Middeke and C. Schneider},
title = {{Denominator Bounds for Higher Order Systems of Linear Recurrence Equations}},
language = {english},
journal = {ACM Communications in Computer Algebra},
volume = {50},
number = {4},
pages = {185--187},
isbn_issn = {ISSN 1932-2240},
year = {2016},
note = {Extended abstract of the poster presentation at ISSAC 2016},
refereed = {no},
length = {2}
}

Rational and Algebraic Solutions of First-Order Algebraic ODEs

N. Thieu Vo

Research Institute for Symbolic Computation. PhD Thesis. 2016. [pdf]
[bib]
@phdthesis{RISC5399,
author = {N. Thieu Vo},
title = {{Rational and Algebraic Solutions of First-Order Algebraic ODEs}},
language = {english},
year = {2016},
translation = {0},
school = {Research Institute for Symbolic Computation},
length = {93}
}

2015

Computation of Dimension in Filtered Free Modules by Gröbner Reduction

Christoph Fuerst, Guenter Landsmann

In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM (ed.), Proceedings of ISSAC '15, pp. 181-188. 2015. 978-1-4503-3435-8. [url]
[bib]
@inproceedings{RISC5154,
author = {Christoph Fuerst and Guenter Landsmann},
title = {{Computation of Dimension in Filtered Free Modules by Gröbner Reduction}},
booktitle = {{Proceedings of the International Symposium on Symbolic and Algebraic Computation}},
language = {english},
pages = {181--188},
isbn_issn = {978-1-4503-3435-8},
year = {2015},
editor = {ACM},
refereed = {yes},
length = {8},
conferencename = {ISSAC '15},
url = {http://doi.acm.org/10.1145/2755996.2756680}
}

Symbolic Solutions of First-Order Algebraic ODEs

G. Grasegger, F. Winkler

In: Computer algebra and polynomials, J. Gutierrez, J. Schicho, M. Weimann (ed.), Lecture Notes in Computer Science 8942, pp. 94-104. 2015. Springer International Publishing, ISSN 0302-9743. [url]
[bib]
@inproceedings{RISC5018,
author = {G. Grasegger and F. Winkler},
title = {{Symbolic Solutions of First-Order Algebraic ODEs}},
booktitle = {{Computer algebra and polynomials}},
language = {english},
series = {Lecture Notes in Computer Science},
volume = {8942},
pages = {94--104},
publisher = {Springer International Publishing},
isbn_issn = {ISSN 0302-9743},
year = {2015},
editor = {J. Gutierrez and J. Schicho and M. Weimann},
refereed = {yes},
length = {11},
url = {http://dx.doi.org/10.1007/978-3-319-15081-9_5}
}

Symbolic solutions of first-order algebraic differential equations

Georg Grasegger

Johannes Kepler University Linz. PhD Thesis. 06 2015. [url]
[bib]
@phdthesis{RISC5160,
author = {Georg Grasegger},
title = {{Symbolic solutions of first-order algebraic differential equations}},
language = {english},
year = {2015},
month = {06},
translation = {0},
school = {Johannes Kepler University Linz},
length = {154},
url = {http://epub.jku.at/obvulihs/content/titleinfo/753082}
}

Automated Reasoning in Reduction Rings using the Theorema System

A. Maletzky

In: Computer Algebra in Scientific Computing, Vladimir P. Gerdt and Wolfram Koepf and Werner M. Seiler and Evgenii V. Vorozhtsov (ed.), Proceedings of CASC 2015 (September 14-18, Aachen, Germany), LNCS 9301, pp. 305-319. 2015. Springer-Verlag Berlin Heidelberg, ISSN 0302-9743. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-24021-3_23. [url] [pdf]
[bib]
@inproceedings{RISC5151,
author = {A. Maletzky},
title = {{Automated Reasoning in Reduction Rings using the Theorema System}},
booktitle = {{Computer Algebra in Scientific Computing}},
language = {english},
series = {LNCS},
volume = {9301},
pages = {305--319},
publisher = {Springer-Verlag Berlin Heidelberg},
isbn_issn = {ISSN 0302-9743},
year = {2015},
note = {The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-24021-3_23},
editor = {Vladimir P. Gerdt and Wolfram Koepf and Werner M. Seiler and Evgenii V. Vorozhtsov},
refereed = {yes},
length = {15},
conferencename = {CASC 2015 (September 14-18, Aachen, Germany)},
url = {http://dx.doi.org/10.1007/978-3-319-24021-3_23}
}

A Note on a Problem Proposed by Kim and Lisonek

Cristian-Silviu Radu

In: Computer Algebra and Polynomials, Jaime Gutierrez, Josef Schicho and Martin Weimann (ed.), Lecture notes in Computer Science , pp. 151-156. 2015. Springer, 978-3-319-15080-2.
[bib]
@incollection{RISC5156,
author = {Cristian-Silviu Radu},
title = {{A Note on a Problem Proposed by Kim and Lisonek}},
booktitle = {{Computer Algebra and Polynomials}},
language = {english},
series = {Lecture notes in Computer Science},
pages = {151--156},
publisher = {Springer},
isbn_issn = { 978-3-319-15080-2},
year = {2015},
editor = { Jaime Gutierrez and Josef Schicho and Martin Weimann},
refereed = {yes},
length = {6}
}

Loading…