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

2023

[Mitteramskogler]

General solutions of first-order algebraic ODEs in simple constant extensions

J. J. Mitteramskogler, F. Winkler

Journal of Systems Science and Complexity (JSSC), pp. 0-0. 2023. 1009-6124.
[bib]
@article{RISC6674,
author = {J. J. Mitteramskogler and F. Winkler},
title = {{General solutions of first-order algebraic ODEs in simple constant extensions}},
language = {english},
journal = {Journal of Systems Science and Complexity (JSSC)},
pages = {0--0},
isbn_issn = {1009-6124},
year = {2023},
refereed = {yes},
length = {0}
}

2022

[Falkensteiner]

On Formal Power Series Solutions of Algebraic Ordinary Differential Equations

S. Falkensteiner, Yi Zhang, N. Thieu Vo

Mediterranean Journal of Mathematics 19(74), pp. 1-16. March 2022. ISSN 1660-5446. [doi]
[bib]
@article{RISC6490,
author = {S. Falkensteiner and Yi Zhang and N. Thieu Vo},
title = {{On Formal Power Series Solutions of Algebraic Ordinary Differential Equations}},
language = {english},
journal = {Mediterranean Journal of Mathematics},
volume = {19},
number = {74},
pages = {1--16},
isbn_issn = {ISSN 1660-5446},
year = {2022},
month = {March},
refereed = {yes},
keywords = {Formal power series, algebraic differential equation.},
length = {16},
url = {https://doi.org/10.1007/s00009-022-01984-w}
}
[Grasegger]

Zero-Sum Cycles in Flexible Non-triangular Polyhedra

Matteo Gallet, Georg Grasegger, Jan Legerský, Josef Schicho

In: 2nd IMA Conference on Mathematics of Robotics, W. Holderbaum, J.M. Selig (ed.), Springer Proceedings in Advanced Robotics 21, pp. 137-143. 2022. 978-3-030-91351-9. [doi]
[bib]
@inproceedings{RISC6388,
author = {Matteo Gallet and Georg Grasegger and Jan Legerský and Josef Schicho},
title = {{Zero-Sum Cycles in Flexible Non-triangular Polyhedra}},
booktitle = {{2nd IMA Conference on Mathematics of Robotics}},
language = {english},
series = {Springer Proceedings in Advanced Robotics},
volume = {21},
pages = {137--143},
isbn_issn = {978-3-030-91351-9},
year = {2022},
editor = {W. Holderbaum and J.M. Selig},
refereed = {yes},
length = {7},
url = {https://doi.org/10.1007/978-3-030-91352-6_14}
}
[Grasegger]

Zero-sum Cycles in Flexible Polyhedra

M. Gallet, G. Grasegger, J. Legersky, J. Schicho

Bull. LMS 54, pp. 112-125. 2022. 1469-2120.
[bib]
@article{RISC6662,
author = {M. Gallet and G. Grasegger and J. Legersky and J. Schicho},
title = {{Zero-sum Cycles in Flexible Polyhedra}},
language = {english},
journal = {Bull. LMS},
volume = {54},
pages = {112--125},
isbn_issn = {1469-2120},
year = {2022},
refereed = {yes},
length = {14}
}
[Mitteramskogler]

Symbolic solutions of algebraic ODEs - A comparison of methods

J. J. Mitteramskogler, F. Winkler

Publicationes Mathematicae Debrecen 100(1-2), pp. 143-166. 2022. 0033-3883.
[bib]
@article{RISC6673,
author = {J. J. Mitteramskogler and F. Winkler},
title = {{Symbolic solutions of algebraic ODEs -- A comparison of methods}},
language = {english},
journal = {Publicationes Mathematicae Debrecen},
volume = {100},
number = {1-2},
pages = {143--166},
isbn_issn = {0033-3883},
year = {2022},
refereed = {yes},
length = {23}
}
[Schicho]

And Yet it Moves - Paradoxically Moving Linkages in Kinematics

J. Schicho

Bulletin AMS 59, pp. 59-95. 2022. ISSN 0273-0979. [doi]
[bib]
@article{RISC6474,
author = {J. Schicho},
title = {{And Yet it Moves -- Paradoxically Moving Linkages in Kinematics}},
language = {english},
journal = {Bulletin AMS},
volume = {59},
pages = {59--95},
isbn_issn = {ISSN 0273-0979},
year = {2022},
refereed = {yes},
length = {37},
url = {https://doi.org/10.1090/bull/1721}
}
[Schicho]

Classification of higher mobility closed-loop linkages

T. Duarte Guerreiro, Z. Li, J. Schicho

Annali di Matematica Pura et Applicata, pp. -. 2022. 0373-3114.
[bib]
@article{RISC6663,
author = {T. Duarte Guerreiro and Z. Li and J. Schicho},
title = {{Classification of higher mobility closed-loop linkages}},
language = {english},
journal = {Annali di Matematica Pura et Applicata},
pages = {--},
isbn_issn = {0373-3114},
year = {2022},
refereed = {yes},
length = {0}
}
[Schicho]

A new line-symmetric mobile infinity-pod

M. Gallet, J. Schicho

Confl. Math. 14, pp. 35-47. 2022. 1793-7442.
[bib]
@article{RISC6664,
author = {M. Gallet and J. Schicho},
title = {{A new line-symmetric mobile infinity-pod}},
language = {english},
journal = {Confl. Math.},
volume = {14},
pages = {35--47},
isbn_issn = {1793-7442},
year = {2022},
refereed = {yes},
length = {13}
}
[Schicho]

Projective isomorphisms between rational surfaces

B. J�ttler, N. Lubbes, J. Schicho

J. Algebra 54, pp. 112-125. 2022. 0021-8693.
[bib]
@article{RISC6668,
author = {B. J�ttler and N. Lubbes and J. Schicho},
title = {{Projective isomorphisms between rational surfaces}},
language = {english},
journal = {J. Algebra},
volume = {54},
pages = {112--125},
isbn_issn = { 0021-8693},
year = {2022},
refereed = {yes},
length = {14}
}

2021

[Grasegger]

Combinatorics of Bricard's octahedra

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

Comptes Rendus. Mathématique 359(1), pp. 7-38. 2021. Académie des sciences, Paris, ISSN 1631-073X. [doi]
[bib]
@article{RISC6288,
author = {M. Gallet and G. Grasegger and J. Legerský and J. Schicho},
title = {{Combinatorics of Bricard's octahedra}},
language = {english},
journal = {Comptes Rendus. Mathématique},
volume = {359},
number = {1},
pages = {7--38},
publisher = {Académie des sciences, Paris},
isbn_issn = {ISSN 1631-073X},
year = {2021},
refereed = {yes},
length = {32},
url = {https://doi.org/10.5802/crmath.132}
}
[Grasegger]

On the Existence of Paradoxical Motions of Generically Rigid Graphs on the Sphere

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

SIAM Journal on Discrete Mathematics 35(1), pp. 325-361. 2021. ISSN 0895-4801. [doi]
[bib]
@article{RISC6290,
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},
journal = {SIAM Journal on Discrete Mathematics},
volume = {35},
number = {1},
pages = {325--361},
isbn_issn = {ISSN 0895-4801},
year = {2021},
refereed = {yes},
length = {37},
url = {https://doi.org/10.1137/19M1289467}
}
[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. [doi]
[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}
}
[Winkler]

My Life in Computer Algebra

F. Winkler

Technical report no. 21-12 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). June 2021. Licensed under CC BY 4.0 International. [doi] [pdf]
[bib]
@techreport{RISC6329,
author = {F. Winkler},
title = {{My Life in Computer Algebra}},
language = {english},
abstract = {After having spent more than 40 years in Mathematics, and in particular in Computer Algebra, I recollect stages in my scientific career and I explain the connections between my different areas of interest.},
number = {21-12},
year = {2021},
month = {June},
keywords = {computer algebra, biography},
length = {19},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}

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. [doi]
[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. [doi]
[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]

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. [doi]
[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]

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. [doi]
[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}
}

Loading…