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

2019

[Legersky]

Flexible and Rigid Labelings of Graphs

Jan Legerský

Research Institute for Symbolic Computation, Johannes Kepler University Linz. PhD Thesis. 2019. [url] [pdf]
[bib]
@phdthesis{RISC5941,
author = {Jan Legerský},
title = {{Flexible and Rigid Labelings of Graphs}},
language = {english},
year = {2019},
translation = {0},
school = {Research Institute for Symbolic Computation, Johannes Kepler University Linz},
length = {108},
url = {https://jan.legersky.cz/project/movablegraphs/}
}
[Schicho]

Projective and affine symmetries and equivalences of rational and polynomial surfaces

M. Hauer, B. Jüttler, J. Schicho

J. Comp. Appl. Math. 349, pp. 424-437. 2019. 0377-0427.
[bib]
@article{RISC5875,
author = {M. Hauer and B. Jüttler and J. Schicho},
title = {{Projective and affine symmetries and equivalences of rational and polynomial surfaces}},
language = {english},
journal = {J. Comp. Appl. Math.},
volume = {349},
pages = {424--437},
isbn_issn = {0377-0427},
year = {2019},
refereed = {yes},
length = {14}
}

2018

[AUTHOR]

Varieties of apolar subschemes of toric surfaces

Gallet Matteo, Ranestad Kristian, Villamizar Nelly

Ark. Mat. 56(1), pp. 73-99. 2018. ISSN 0004-2080. [url]
[bib]
@article{RISC5796,
author = {Gallet Matteo and Ranestad Kristian and Villamizar Nelly},
title = {{Varieties of apolar subschemes of toric surfaces}},
language = {english},
journal = {Ark. Mat.},
volume = {56},
number = {1},
pages = {73--99},
isbn_issn = { ISSN 0004-2080},
year = {2018},
refereed = {yes},
length = {27},
url = {https://doi.org/10.4310/ARKIV.2018.v56.n1.a6}
}
[Grasegger]

Graphs with Flexible Labelings

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

Discrete & Computational Geometry, pp. 1-20. 2018. 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},
pages = {1--20},
isbn_issn = {1432-0444},
year = {2018},
note = {arXiv:1708.05298},
refereed = {yes},
length = {20},
url = {https://doi.org/10.1007/s00454-018-0026-9}
}
[Grasegger]

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}
}
[Grasegger]

Graphs with Flexible Labelings allowing Injective Realizations

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

arXiv. Technical report, 2018. [url]
[bib]
@techreport{RISC5806,
author = {G. Grasegger and J. Legerský and J. Schicho},
title = {{Graphs with Flexible Labelings allowing Injective Realizations}},
language = {english},
year = {2018},
institution = {arXiv},
length = {21},
url = {https://arxiv.org/abs/1811.06709}
}
[Grasegger]

Rational general solutions of systems of first-order algebraic partial differential equations

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

J. Computational and Applied Mathematics(331), pp. 88-103. 2018. ISSN 0377-0427. [pdf]
[bib]
@article{RISC5837,
author = {G. Grasegger and A. Lastra and J.R. Sendra and F. Winkler},
title = {{Rational general solutions of systems of first-order algebraic partial differential equations}},
language = {english},
journal = {J. Computational and Applied Mathematics},
number = {331},
pages = {88--103},
isbn_issn = {ISSN 0377-0427},
year = {2018},
refereed = {yes},
length = {16}
}
[Grasegger]

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. [pdf]
[bib]
@article{RISC5838,
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},
number = {87},
pages = {127--139},
isbn_issn = {ISSN 0747-7171},
year = {2018},
refereed = {yes},
length = {13}
}
[Koutschan]

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}
}
[Legersky]

On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs

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

In: ISSAC '18 Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, C. Arreche (ed.), Proceedings of International Symposium on Symbolic and Algebraic Computation 2018, pp. 55-62. 2018. 978-1-4503-5550-6. [url]
[bib]
@inproceedings{RISC5804,
author = {E. Bartzos and I.Z. Emiris and J. Legerský and E. Tsigaridas},
title = {{On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs}},
booktitle = {{ISSAC '18 Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation}},
language = {english},
pages = {55--62},
isbn_issn = {978-1-4503-5550-6},
year = {2018},
editor = {C. Arreche},
refereed = {yes},
length = {8},
conferencename = {International Symposium on Symbolic and Algebraic Computation 2018},
url = {https://doi.org/10.1145/3208976.3208994}
}
[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

arXiv. Technical report, 2018. [url]
[bib]
@techreport{RISC5810,
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},
year = {2018},
institution = {arXiv},
length = {22},
url = {https://arxiv.org/abs/1811.12800}
}
[McCallum]

Resultants: Algebraic and Differential

S. McCallum, F. Winkler

Technical report no. 18-08 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. August 2018. [pdf]
[bib]
@techreport{RISC5735,
author = {S. McCallum and F. Winkler},
title = {{Resultants: Algebraic and Differential}},
language = {english},
abstract = {This report summarises ongoing discussions of the authors on the topic of differential resultantswhich have three goals in mind. First, we aim to try to understand existing literature on thetopic. Second, we wish to formulate some interesting questions and research goals based on ourunderstanding of the literature. Third, we would like to advance the subject in one or moredirections, by pursuing some of these questions and research goals. Both authors have somewhatmore background in nondifferential, as distinct from differential, computational algebra. For thisreason, our approach to learning about differential resultants has started with a careful review ofthe corresponding theory of resultants in the purely algebraic (polynomial) case. We try, as faras possible, to adapt and extend our knowledge of purely algebraic resultants to the differentialcase. Overall, we have the hope of helping to clarify, unify and further develop the computationaltheory of differential resultants.},
number = {18-08},
year = {2018},
month = {August},
length = {21},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Schloss Hagenberg, 4232 Hagenberg, Austria}
}
[McCallum]

Differential Resultants, in Recent Advances in Algebra, Numerical Analysis and Statistics

S. McCallum, F. Winkler

In: Proc. Internat. Conf. on Mathematics (ICM 2018), R. Bris et al. (ed.), Proceedings of ICM 2018, pp. 1-11. Dezember 2018. Ton Duc Thang University (TDTU), Ho Chi Minh City, Vietnam, ISBN 978-2-7598-9058-3. [url] [pdf]
[bib]
@inproceedings{RISC5842,
author = {S. McCallum and F. Winkler},
title = {{Differential Resultants, in Recent Advances in Algebra, Numerical Analysis and Statistics}},
booktitle = {{Proc. Internat. Conf. on Mathematics (ICM 2018)}},
language = {english},
pages = {1--11},
isbn_issn = {ISBN 978-2-7598-9058-3},
year = {2018},
month = {Dezember},
editor = {R. Bris et al.},
refereed = {yes},
institution = {Ton Duc Thang University (TDTU), Ho Chi Minh City, Vietnam},
length = {11},
conferencename = {ICM 2018},
url = {http://icm2018.tdtu.edu.vn/}
}
[Schicho]

Kinematic generation of Darboux cyclides

N. Lubbes, J. Schicho

Comp. Aided Geom. Des. 64, pp. -. 2018. 0167-8396.
[bib]
@article{RISC5876,
author = {N. Lubbes and J. Schicho},
title = {{Kinematic generation of Darboux cyclides}},
language = {english},
journal = {Comp. Aided Geom. Des.},
volume = {64},
pages = {--},
isbn_issn = {0167-8396},
year = {2018},
refereed = {yes},
length = {0}
}
[Schicho]

Kempe's Universality Theorem for Rational Space Curves

Z. Li, J. Schicho, H.-P. Schröcker

Found. Comp. Math. 18, pp. 509-536. 2018. 1615-3375.
[bib]
@article{RISC5879,
author = {Z. Li and J. Schicho and H.-P. Schröcker},
title = {{Kempe's Universality Theorem for Rational Space Curves}},
language = {english},
journal = {Found. Comp. Math.},
volume = {18},
pages = {509--536},
isbn_issn = {1615-3375},
year = {2018},
refereed = {yes},
length = {28}
}
[Winkler]

Das Unendliche im mathemtischen Alltag

F. Winkler

In: Beiträge des 41. Internationalen Wittgenstein Symposiums, G.M. Mras, P. Weingartner, B. Ritter (ed.), Proceedings of 41. Internationales Wittgenstein Symposium, pp. 285-287. August 2018. ISSN 1022-3398. [pdf]
[bib]
@inproceedings{RISC5840,
author = {F. Winkler},
title = {{Das Unendliche im mathemtischen Alltag}},
booktitle = {{Beiträge des 41. Internationalen Wittgenstein Symposiums}},
language = {english},
pages = {285--287},
isbn_issn = {ISSN 1022-3398},
year = {2018},
month = {August},
editor = {G.M. Mras and P. Weingartner and B. Ritter },
refereed = {yes},
length = {3},
conferencename = {41. Internationales Wittgenstein Symposium}
}

2017

[Fuerst]

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}
}
[Grasegger]

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}
}
[Koutschan]

The number of realizations of a Laman graph

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

Research Institute for Symbolic Computation (RISC/JKU). Technical report, 2017. [url] [pdf]
[bib]
@techreport{RISC5418,
author = {Jose Capco and Georg Grasegger and Matteo Gallet and Christoph Koutschan and Niels Lubbes and Josef Schicho},
title = {{The number of realizations of a Laman graph}},
language = {english},
abstract = {Laman graphs model planar frameworks that 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. Such realizations can be seen as solutions of systems of quadratic equations prescribing the distances between pairs of points. Using ideas from algebraic and tropical geometry, we provide a recursion formula for the number of complex solutions of such systems. },
year = {2017},
institution = {Research Institute for Symbolic Computation (RISC/JKU)},
length = {42},
url = {http://www.koutschan.de/data/laman/}
}
[Koutschan]

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/}
}

Loading…