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.

Software

CASA

Computer Algebra System for Algebraic Geometry

CASA is a special-purpose system for computational algebra and constructive algebraic geometry. The system has been developed since 1990, and is the ongoing product of the Computer Algebra Group under the direction of Prof. Winkler. It is built on the ...

Authors: Franz Winkler
MoreSoftware Website

CharSet

Differential Characteristic Set Computations

CharSet is an Aldor package written by Christian Aistleitner for differential characteristic set computations. CharSet comes with generic implementations of reduction, Gröbner bases, and differential characteristic set algorithms. Interfaces to the command line, Mathematica and Maple are included. ...

More

PGB

Parametric Gröbner Bases

PGB is a software package for computing parametric Gröbner bases and related objects in several domains. It is implemented in the computer algebra system Risa/Asir by Katsusuke Nabeshima. ...

More

Publications

2021

[Legersky]

On the maximal number of real embeddings of minimally rigid graphs in R2, R3 and S2

E. Bartzos, I.Z. Emiris, J. Legerský, E. Tsigaridas

Journal of Symbolic Computation 102, pp. 189-208. 2021. ISSN 0747-7171. [url]
[bib]
@article{RISC5992,
author = {E. Bartzos and I.Z. Emiris and J. Legerský and E. Tsigaridas},
title = {{On the maximal number of real embeddings of minimally rigid graphs in R2, R3 and S2}},
language = {english},
journal = {Journal of Symbolic Computation},
volume = {102},
pages = {189--208},
isbn_issn = {ISSN 0747-7171},
year = {2021},
refereed = {yes},
length = {20},
url = {https://doi.org/10.1016/j.jsc.2019.10.015}
}

2020

[Capco]

Robots, computer algebra and 8 connected components

J. Capco, M. Safey el Din, J. Schicho

In: Proceedings of ISSAC 2020, I. Emiris, L. Zhi (ed.), pp. 62-69. 2020. 978-1-4503-7100-1. [url]
[bib]
@inproceedings{RISC6247,
author = {J. Capco and M. Safey el Din and J. Schicho},
title = {{Robots, computer algebra and 8 connected components}},
booktitle = {{Proceedings of ISSAC 2020}},
language = {english},
pages = {62--69},
isbn_issn = {978-1-4503-7100-1},
year = {2020},
editor = {I. Emiris and L. Zhi},
refereed = {yes},
length = {8},
url = {https://arxiv.org/abs/2008.13392}
}
[Grasegger]

Computing Animations of Linkages with Rotational Symmetry (Media Exposition)

Sean Dewar, Georg Grasegger, Jan Legerský

In: 36th International Symposium on Computational Geometry (SoCG 2020), Sergio Cabello and Danny Z. Chen (ed.), Leibniz International Proceedings in Informatics (LIPIcs) 164, pp. 77:1-77:4. 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, ISBN 978-3-95977-143-6. [url]
[bib]
@inproceedings{RISC6128,
author = {Sean Dewar and Georg Grasegger and Jan Legerský},
title = {{Computing Animations of Linkages with Rotational Symmetry (Media Exposition)}},
booktitle = {{36th International Symposium on Computational Geometry (SoCG 2020)}},
language = {english},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {164},
pages = {77:1--77:4},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
address = {Dagstuhl, Germany},
isbn_issn = {ISBN 978-3-95977-143-6},
year = {2020},
editor = {Sergio Cabello and Danny Z. Chen},
refereed = {no},
length = {4},
url = {https://doi.org/10.4230/LIPIcs.SoCG.2020.77}
}
[Grasegger]

Graphs with Flexible Labelings allowing Injective Realizations

G. Grasegger, J. Legerský, J. Schicho

Discrete Mathematics 343(6), pp. Art. 111713-. 2020. ISSN 0012-365X. [url]
[bib]
@article{RISC6012,
author = {G. Grasegger and J. Legerský and J. Schicho},
title = {{Graphs with Flexible Labelings allowing Injective Realizations}},
language = {english},
journal = {Discrete Mathematics},
volume = {343},
number = {6},
pages = {Art. 111713--},
isbn_issn = {ISSN 0012-365X},
year = {2020},
refereed = {yes},
length = {14},
url = {https://doi.org/10.1016/j.disc.2019.111713}
}
[Grasegger]

Flexible placements of graphs with rotational symmetry

S.Dewar, G. Grasegger, J. Legerský

arXiv. Technical report, 2020. [url]
[bib]
@techreport{RISC6091,
author = {S.Dewar and G. Grasegger and J. Legerský},
title = {{Flexible placements of graphs with rotational symmetry}},
language = {english},
year = {2020},
institution = {arXiv},
length = {9},
url = {https://arxiv.org/abs/2003.09328}
}
[Grasegger]

Combinatorics of Bricard’s octahedra

M. Gallet, G. Grasegger, J. Legerský, J. Schicho

arXiv. Technical report, 2020. [url]
[bib]
@techreport{RISC6095,
author = {M. Gallet and G. Grasegger and J. Legerský and J. Schicho},
title = {{Combinatorics of Bricard’s octahedra}},
language = {english},
year = {2020},
institution = {arXiv},
length = {40},
url = {https://arxiv.org/pdf/2004.01236.pdf}
}
[Grasegger]

FlexRiLoG - A SageMath Package for Motions of Graphs

G. Grasegger, J. Legerský

In: Mathematical Software – ICMS 2020, Bigatti A., Carette J., Davenport J., Joswig M., de Wolff T. (ed.), Proceedings of ICMS 2020, Lecture Notes in Computer Science 12097, pp. 442-450. 2020. Springer, Cham, ISBN 978-3-030-52199-8. [url]
[bib]
@inproceedings{RISC6182,
author = {G. Grasegger and J. Legerský},
title = {{FlexRiLoG - A SageMath Package for Motions of Graphs}},
booktitle = {{ Mathematical Software – ICMS 2020}},
language = {english},
series = {Lecture Notes in Computer Science},
volume = {12097},
pages = {442--450},
publisher = {Springer, Cham},
isbn_issn = {ISBN 978-3-030-52199-8},
year = {2020},
editor = {Bigatti A. and Carette J. and Davenport J. and Joswig M. and de Wolff T.},
refereed = {no},
length = {9},
conferencename = {ICMS 2020},
url = {https://doi.org/10.1007/978-3-030-52200-1_44}
}
[Grasegger]

Bracing frameworks consisting of parallelograms

G. Grasegger, J. Legerský

arXiv. Technical report, 2020. [url]
[bib]
@techreport{RISC6203,
author = {G. Grasegger and J. Legerský},
title = {{Bracing frameworks consisting of parallelograms}},
language = {english},
year = {2020},
institution = {arXiv},
length = {20},
url = {https://arxiv.org/abs/2008.11521}
}
[Grasegger]

Zero-sum cycles in flexible polyhedra

M. Gallet, G. Grasegger, J. Legerský, J. Schicho

arXiv. Technical report, 2020. [url]
[bib]
@techreport{RISC6211,
author = {M. Gallet and G. Grasegger and J. Legerský and J. Schicho},
title = {{Zero-sum cycles in flexible polyhedra}},
language = {english},
year = {2020},
institution = {arXiv},
length = {16},
url = {https://arxiv.org/abs/2009.14041}
}
[Grasegger]

On the Classification of Motions of Paradoxically Movable Graphs

G. Grasegger, J. Legerský, J. Schicho

Journal of Computational Geometry 11(1), pp. 548-575. 2020. ISSN: 1920-180X. [url]
[bib]
@article{RISC6239,
author = {G. Grasegger and J. Legerský and J. Schicho},
title = {{On the Classification of Motions of Paradoxically Movable Graphs}},
language = {english},
journal = {Journal of Computational Geometry},
volume = {11},
number = {1},
pages = {548--575},
isbn_issn = {ISSN: 1920-180X},
year = {2020},
refereed = {yes},
length = {27},
url = {https://doi.org/10.20382/jocg.v11i1a22}
}
[Grasegger]

Counting realizations of {L}aman graphs on the sphere

M. Gallet, G. Grasegger, J. Schicho

Electronic Journal of Combinatorics 27(2), pp. 1-18. 2020. 1077-8926 . [url]
[bib]
@article{RISC6243,
author = {M. Gallet and G. Grasegger and J. Schicho},
title = {{Counting realizations of {L}aman graphs on the sphere}},
language = {english},
journal = {Electronic Journal of Combinatorics},
volume = {27},
number = {2},
pages = {1--18},
isbn_issn = {1077-8926 },
year = {2020},
refereed = {yes},
length = {18},
url = {https://arxiv.org/abs/1903.01145}
}
[Jimenez Pastor]

Some structural results on D^n finite functions

A. Jimenez-Pastor, V. Pillwein, M.F. Singer

Advances in Applied Mathematics 117, pp. 0-0. June 2020. Elsevier, 0196-8858. [url] [pdf]
[bib]
@article{RISC6077,
author = {A. Jimenez-Pastor and V. Pillwein and M.F. Singer},
title = {{Some structural results on D^n finite functions}},
language = {english},
abstract = {D-finite (or holonomic) functions satisfy linear differential equations with polynomial coefficients. They form a large class of functions that appear in many applications in Mathematics or Physics. It is well-known that these functions are closed under certain operations and these closure properties can be executed algorithmically. Recently, the notion of D-finite functions has been generalized to differentially definable or Dn-finite functions. Also these functions are closed under operations such as forming (anti)derivative, addition or multiplication and, again, these can be implemented. In this paper we investigate how Dn-finite functions behave under composition and how they are related to algebraic and differentially algebraic functions.},
journal = {Advances in Applied Mathematics},
volume = {117},
pages = {0--0},
publisher = {Elsevier},
isbn_issn = {0196-8858},
year = {2020},
month = {June},
refereed = {yes},
length = {0},
url = {https://doi.org/10.1016/j.aam.2020.102027}
}
[Mitteramskogler]

Symbolic solutions of algebraic ODEs - A comparison of methods

Franz Winkler, Johann Mitteramskogler

Publications Mathemticae Debrecen, pp. 0-0. 2020. 0.
[bib]
@article{RISC6253,
author = {Franz Winkler and Johann Mitteramskogler},
title = {{Symbolic solutions of algebraic ODEs -- A comparison of methods}},
language = {english},
journal = {Publications Mathemticae Debrecen},
pages = {0--0},
isbn_issn = {0},
year = {2020},
refereed = {yes},
length = {0}
}
[Radu]

A Reduction Theorem of Certain Relations Modulo p Involving Modular Forms

Radu, Cristian-Silviu

In: Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra, in Honour of Peter Paule on his 60th Birthday, V. Pillwein, C. Schneider (ed.), pp. 1-15. 2020. Springer, 978-3-030-44558-4. [pdf]
[bib]
@incollection{RISC6110,
author = {Radu and Cristian-Silviu},
title = {{A Reduction Theorem of Certain Relations Modulo p Involving Modular Forms}},
booktitle = {{Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra, in Honour of Peter Paule on his 60th Birthday}},
language = {english},
pages = {1--15},
publisher = {Springer},
isbn_issn = {978-3-030-44558-4},
year = {2020},
editor = {V. Pillwein and C. Schneider},
refereed = {yes},
length = {15}
}
[Schicho]

Probabilities of incidence between lines and a plane curve over finite field

M. Gallet, M. Makhul, J. Schicho

Finite Fields and Their Applications 61, pp. 1-22. 2020. 1071-5797.
[bib]
@article{RISC6073,
author = {M. Gallet and M. Makhul and J. Schicho},
title = {{Probabilities of incidence between lines and a plane curve over finite field}},
language = {english},
journal = {Finite Fields and Their Applications},
volume = {61},
pages = {1--22},
isbn_issn = {1071-5797},
year = {2020},
refereed = {yes},
length = {22}
}
[Schicho]

On the multihomogeneous Bezout bound on the number of embeddings of minimally rigid graphs

V. Bartzos, I. Emiris, J. Schicho

Applicable Algebra in Engineering, Communication and Computing 31, pp. 325-357. 2020. 0938-1279. [url]
[bib]
@article{RISC6245,
author = {V. Bartzos and I. Emiris and J. Schicho},
title = {{On the multihomogeneous Bezout bound on the number of embeddings of minimally rigid graphs}},
language = {english},
journal = {Applicable Algebra in Engineering, Communication and Computing},
volume = {31},
pages = {325--357},
isbn_issn = {0938-1279},
year = {2020},
refereed = {yes},
length = {32},
url = {https://arxiv.org/abs/2005.14485}
}
[Schicho]

Counting Projections of Rational Curves

M. Gallet, J. Schicho

Israel Journal of Mathematics 240, pp. 503-538. 2020. 0021-2172 . [url]
[bib]
@article{RISC6246,
author = {M. Gallet and J. Schicho},
title = {{Counting Projections of Rational Curves}},
language = {english},
journal = {Israel Journal of Mathematics},
volume = {240},
pages = {503--538},
isbn_issn = {0021-2172 },
year = {2020},
refereed = {yes},
length = {36},
url = {https://arxiv.org/abs/1707.05264}
}
[Winkler]

Symbolic computation in algebra, geometry, and differential equations

Franz Winkler

In: Proceedings CAI-2019, , Special issue of "Information and Computation" , pp. 0-0. 2020. 0.
[bib]
@inproceedings{RISC6252,
author = {Franz Winkler},
title = {{Symbolic computation in algebra, geometry, and differential equations}},
booktitle = {{Proceedings CAI-2019}},
language = {english},
series = {Special issue of "Information and Computation"},
pages = {0--0},
isbn_issn = {0},
year = {2020},
editor = {?},
refereed = {yes},
length = {0}
}

2019

[Grasegger]

Graphs with Flexible Labelings

G. Grasegger, J. Legerský, J. Schicho

Discrete & Computational Geometry 62(2), pp. 461-480. 2019. 1432-0444. arXiv:1708.05298. [url]
[bib]
@article{RISC5803,
author = {G. Grasegger and J. Legerský and J. Schicho},
title = {{Graphs with Flexible Labelings}},
language = {english},
journal = {Discrete & Computational Geometry},
volume = {62},
number = {2},
pages = {461--480},
isbn_issn = {1432-0444},
year = {2019},
note = {arXiv:1708.05298},
refereed = {yes},
length = {20},
url = {https://doi.org/10.1007/s00454-018-0026-9}
}
[Grasegger]

On the existence of paradoxical motions of generically rigid graphs on the sphere

M. Gallet, G. Grasegger, J. Legerský, J. Schicho

arXiv. Technical report, 2019. [url]
[bib]
@techreport{RISC5977,
author = {M. Gallet and G. Grasegger and J. Legerský and J. Schicho},
title = {{On the existence of paradoxical motions of generically rigid graphs on the sphere}},
language = {english},
year = {2019},
institution = {arXiv},
length = {40},
url = {https://arxiv.org/abs/1908.00467}
}

Loading…