Since the ancient times, mathematicians were developing computational and algorithmic tools in order to answer the various mathematical questions or daily problems they faced. In the beginning of last century, the research focus of mathematicians shifted from computational to existential problems, but during the last decades, the long line of research in computational mathematics was restored. My work is following this line of research, on effective theory and algorithms.

My research interests span the area between combinatorics, polyhedral geometry, number theory and algebra. More precisely, the tools I am using come mostly from polyhedral geometry and computational algebraic geometry (computer algebra), while the problems I am trying to solve come from combinatorics, number theory, algebra or any of their intersections. I am mostly interested in research topics combining tools from different areas. Except for the intrinsic importance of interdisciplinary research, another reason is that knowledge transfer, more often than not, leads to better algorithmic solutions. Algorithms bind together the aforementioned areas as far as my interests are concerned. In particular, algorithms from polyhedral and algebraic geometry can be used in order to devise algorithms to solve combinatorial or number theoretic problems and vice versa. During the process, one gains insight on the resulting algorithm by connecting to something known, but often also improves the algorithmic tool itself.

The two main themes of my research are algorithmic enumeration and change of representation. In order to achieve my research goals, the computation of bases and decompositions becomes necessary.

Algorithmic Enumeration

Enumeration can be thought of as either counting or listing the elements of a set. A number of problems can be viewed as enumeration problems, e.g., counting or listing

non-negative integer solutions to linear systems
integer partitions
lattice points in polyhedra
(complex, real, etc.) roots of algebraic systems
magic squares and other combinatorial structures
orthogonal designs

Since the algorithmic solution of enumeration problems is essential, their algorithmic complexity is important. Some of these problems are easy in terms of complexity, while others are hard. For example, real root counting for univariate polynomials is polynomial-time solvable, while the enumeration of non-negative integer solutions to linear systems is NP-hard.

One of the first problems one encounters when trying to solve enumeration problems is how to enumerate an infinite set of objects. Generating functions is a standard tool addressing this problem. For simplicity, and because this is the most used case in my research, let’s assume \(S\) is a subset of \(\mathbb{N}^d\) for some \(d\in\mathbb{N}^{*}\). Then we define \(\Phi_{z}^{S}\), the generating function of \(S\), to be the formal sum \(\Phi_{z}^{S}=\sum_{\alpha\in S}^{} z^\alpha,\) where \(z^\alpha=z_1^{\alpha_1}z_2^{\alpha_2}\cdots z_n^{\alpha_d}\) (multi-index notation). If there exists a rational function which has \(\Phi_{z}^{S}\) as a series expansion, then we denote it by \(\rho_{z}^{S}\) and call it a rational generating function of \(S\).

Obviously, in the case of infinite sets the notion of counting is not valid anymore, although in some cases it is possible that refined counting is both feasible and useful. For example, if we consider integer partitions, we can formulate the problem of listing all integer partitions, i.e., the set of all finite and non-decreasing sequences of integers greater than zero denoted by \(S\). The corresponding generating function is \(\displaystyle \sum_{s\in S} z^s.\) Although the listing problem is valid, the counting problems is meaningless, since their number is obviously infinite. One can consider though, the integer partitions of an integer \(n\), denoted by \(S_n\). In that case, the number of partitions is finite for arbitrary but fixed \(n\) and thus both the listing and the counting problems are meaningful. For the listing problem we have the generating function \(\displaystyle \sum_{n=1}^{\infty} q^n \sum_{s\in S_n} z^s,\) while for the counting problem the generating function is \(\displaystyle \sum_{n=1}^{\infty} q^n \big| S_n \big| = \left(\sum_{n=1}^{\infty} q^n \left(\sum_{s\in S_n} z^s\right)\right)_{z_i=1}.\) This refined counting, where \(n\) is a parameter defining the clustering of integer partitions, can be refined further. For example, we can ask for the integer partitions of \(n\) consisting of \(k\) parts. On the other hand, we could have also used the number of parts \(k\), as the refining parameter alone. All of the problems above are of interest as enumeration problems in integer partition theory.

The problems in algorithmic enumeration that I have studied and are still part of my research plan include the solution of linear Diophantine systems and the computation of rational generating functions for integer partitions under linear constraints, the computation of rational generating functions for the lattice points in polyhedra of infinite dimension, the algorithmic treatment of identities concerning integer partitions and their generating functions, the efficient computation of Ehrhart polynomials, computing the directional multiplicity of isolated points in affine varieties, and the counting of real roots of algebraic systems (Zafeirakopoulos, 2008).

Change of Representation

The second major theme of my research is change of representation. In order to combine the theory and the algorithmic tools from different areas of mathematics, it is essential to transform the representation of an object from one area to the representation used in another. A typical example is the representation of solutions to linear Diophantine systems, which can be taken as a semigroup from a classical algebraic viewpoint, or the set of constrained integer partitions in the context of number theory, or the set of lattice points in a polyhedron when represented as a polyhedral-geometric object.

This identification of the different representations is not always easy, but it is almost always helpful. Different properties of the object are better understood under different representations. Moreover, one can exploit the different representations algorithmically to achieve better results. The former can be seen in (Beck et al., 2016), where the self-reciprocity of the generating function for Lecture Hall partitions is studied in the context of Gorenstein cones. The latter is evident in the development of the Polyhedral Omega algorithm in (Breuer & Zafeirakopoulos, 2017). Often it is important to have two representations of an object, since for some question the first representation is more convenient while for other questions it is the second. For example, if we want to check if a point belongs to a curve, then the implicit form is better (Emiris et al., 2015). If we want to plot the curve though, the parametric form (Katsamaki et al., 2023) is better.

The change of representation theme, appears in my research clearly in the treatment of integer partitions as lattice points in polyhedra and in the consideration of the Ehrhart polynomial computation as an interpolation problem, which in turn becomes again a problem in polyhedral geometry (Fisikopoulos & Zafeirakopoulos, 2017).

Bases and Decomposition

Through the change of representation, one of the major goals is to obtain a more concise and complete description of the object. It is very usual and natural, to resort in the computation of some kind of basis for the model we created.

In the realm of algebraic systems, the most usual tools I employ are Gr"obner and dual bases. Their study is of independent interest (Mantzaflaris et al., 2016; Rahkooy & Zafeirakopoulos, 2011), but also an integral part of the study of other problems (Koukouvinos et al., 2011; Koukouvinos et al., 2013).

A tool that provides a lot of information when dealing with polyhedral objects is a basis for the underlying semigroup structure, i.e., the Hilbert basis of the saturation of the semigroup defined by the generators of a cone. During my research, I mostly used Brion and Lawrence-Varchenko decompositions of polyhedra into simplicial cones. On the other hand, in the context of implicitization (Emiris et al., 2015), we used Minkowski decomposition in order to compute the Newton polytope of the implicit equation.

Optimization

Finally, after having the algorithmic tools and useful descriptions of our objects, the next natural question is to optimize a linear functional over those objects. In general, various forms of discrete optimization arise within my research. In particular, I am interested in Integer Linear Programming, since it is the optimization version of solving linear Diophantine systems. In addition, a lot of problems can be approached as Integer Linear Programs (e.g., we currently study polynomial multiplication in this setting). Clearly the methods coming from this research lead to general solutions and thus not expected to perform better than the excellent existing heuristics. The goal is to study the geometry of problem families and detect families where our tools may perform well.

The one sentence statement of my research plan is to “develop and implement algorithms, combining geometry and algebra, for the treatment of enumeration and optimization in problems coming from combinatorics and number theory”.

Publications

Volumes edited

2023

Special Issue for 27th International Conference on Applications of Computer Algebra (Istanbul, August 2022), Selected papers

2023

2020

Mathematical Aspects of Computer and Information Sciences - 8th International Conference, MACIS 2019, Gebze, Turkey, November 13-15, 2019, Revised Selected Papers

2020

Journal articles

2023

PTOPO: Computing the geometry and the topology of parametric curves

Christina Katsamaki, Fabrice Rouillier, Elias Tsigaridas, and Zafeirakis Zafeirakopoulos

Journal of Symbolic Computation, 2023

Abs arXiv Bib Code

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rn. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients τ, then the worst case bit complexity of PTOPO is O˜B(nd6+nd5τ+d4(n2+nτ)+d3(n2τ+n3)+n3d2τ). This bound matches the current record bound O˜B(d6+d5τ) for the problem of computing the topology of a plane algebraic curve given in implicit form. For plane and space curves, if N=max⁡d,τ, the complexity of PTOPO becomes O˜B(N6), which improves the state-of-the-art result, due to Alcázar and Díaz-Toca [CAGD’10], by a factor of N10. In the same time complexity, we obtain a graph whose straight-line embedding is isotopic to the curve. However, visualizing the curve on top of the abstract graph construction, increases the bound to O˜B(N7). For curves of general dimension, we can also distinguish between ordinary and non-ordinary real singularities and determine their multiplicities in the same expected complexity of PTOPO by employing the algorithm of Blasco and Pérez-Díaz [CAGD’19]. We have implemented PTOPO in maple for the case of plane and space curves. Our experiments illustrate its practical nature.
@article{ptopo2023, title = {PTOPO: Computing the geometry and the topology of parametric curves}, journal = {Journal of Symbolic Computation}, volume = {115}, pages = {427-451}, year = {2023}, issn = {0747-7171}, doi = {https://doi.org/10.1016/j.jsc.2022.08.012}, url = {https://www.sciencedirect.com/science/article/pii/S0747717122000785}, author = {Katsamaki, Christina and Rouillier, Fabrice and Tsigaridas, Elias and Zafeirakopoulos, Zafeirakis}, keywords = {Parametric curve, Topology, Bit complexity, Polynomial systems}, bibtex_show = true, selected = true, }

2017

Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems

Felix Breuer, and Zafeirakis Zafeirakopoulos

Annals of Combinatorics, Jun 2017

Abs arXiv Bib Code

Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omegacombines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon’s iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok’s short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omegais significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omegathe simplest algorithm for solving linear Diophantine systems available to date. Moreover, we provide an illustrated geometric interpretation of partition analysis, with the aim of making ideas from both areas accessible to readers from a wide range of backgrounds.
@article{Breuer2017, author = {Breuer, Felix and Zafeirakopoulos, Zafeirakis}, title = {Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems}, journal = {Annals of Combinatorics}, year = {2017}, month = jun, day = {01}, volume = {21}, number = {2}, pages = {211--280}, issn = {0219-3094}, doi = {10.1007/s00026-017-0349-x}, url = {https://doi.org/10.1007/s00026-017-0349-x}, bibtex_show = true, selected = true, }

2016

Generating Functions and Triangulations for Lecture Hall Cones

Matthias Beck, Benjamin Braun, Matthias Köppe, Carla D. Savage, and Zafeirakis Zafeirakopoulos

SIAM Journal on Discrete Mathematics, Jun 2016

Abs arXiv Bib

We investigate the arithmetic-geometric structure of the lecture hall cone \(L_n = \left\lbraceλ∈\mathbbR^n:  0≤\frac\lambda_11≤\frac\lambda_22≤\frac\lambda_33≤⋯≤\frac\lambda_nn\right\rbrace\). We show that \(L_n\)is isomorphic to the cone over the lattice pyramid of a reflexive simplex whose Ehrhart \(h^*\)-polynomial is given by the \((n-1)\)st Eulerian polynomial and prove that lecture hall cones admit regular, flag, unimodular triangulations. After explicitly describing the Hilbert basis for \(L_n\), we conclude with observations and a conjecture regarding the structure of unimodular triangulations of \(L_n\), including connections between enumerative and algebraic properties of \(L_n\)and cones over unit cubes.
@article{Beck2016, author = {Beck, Matthias and Braun, Benjamin and K\"{o}ppe, Matthias and Savage, Carla D. and Zafeirakopoulos, Zafeirakis}, title = {Generating Functions and Triangulations for Lecture Hall Cones}, journal = {SIAM Journal on Discrete Mathematics}, volume = {30}, number = {3}, pages = {1470-1479}, year = {2016}, doi = {10.1137/15M1036907}, url = {https://doi.org/10.1137/15M1036907}, eprint = {https://doi.org/10.1137/15M1036907}, bibtex_show = true, selected = true, }
Efficient computation of dual space and directional multiplicity of an isolated point

Angelos Mantzaflaris, Hamid Rahkooy, and Zafeirakis Zafeirakopoulos

Computer Aided Geometric Design , Jun 2016

SI: New Developments Geometry

2014

s-Lecture hall partitions, self-reciprocal polynomials, and Gorenstein cones

Matthias Beck, Benjamin Braun, Matthias Köppe, Carla D. Savage, and Zafeirakis Zafeirakopoulos

The Ramanujan Journal, Jun 2014

arXiv Bib

@article{beck2012s,
  year = {2014},
  issn = {1382-4090},
  journal = {The Ramanujan Journal},
  doi = {10.1007/s11139-013-9538-3},
  title = {s-Lecture hall partitions, self-reciprocal polynomials, and Gorenstein cones},
  url = {http://dx.doi.org/10.1007/s11139-013-9538-3},
  publisher = {Springer US},
  keywords = {Lecture hall partition; Polyhedral cone; Generating function; Gorenstein; Self-reciprocal polynomial; 05A17; 05A19; 52B11; 13A02; 13H10},
  author = {Beck, Matthias and Braun, Benjamin and K\"oppe, Matthias and Savage, Carla D. and Zafeirakopoulos, Zafeirakis},
  pages = {1-25},
  language = {English},
  bibtex_show = true,
}

2011

On the average complexity for the verification of compatible sequences

Christos Koukouvinos, Veronika Pillwein, Dimitris E. Simos, and Zafeirakis Zafeirakopoulos

Information Processing Letters, Jun 2011

Conference Articles

2020

On the geometry and the topology of parametric curves

Christina Katsamaki, Fabrice Rouillier, Elias P. Tsigaridas, and Zafeirakis Zafeirakopoulos

In ISSAC ’20: International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020, Jun 2020

2019

A Machine Learning Framework for Volume Prediction

Umutcan Önal, and Zafeirakis Zafeirakopoulos

In Analysis of Experimental Algorithms, Jun 2019

Abs

Computing the exact volume of a polytope is a #P-hard problem, which makes the computation for high dimensional polytopes computationally expensive. Due to this cost of computation, randomized approximation algorithms is an acceptable solution in practical applications. On the other hand, machine learning techniques, such as neural networks, saw a lot of success in recent years. We propose machine learning approaches to volume prediction and volume comparison. We employ various network architectures such as feed-forward networks, autoencoders and end-to-end networks. We develop different types of models with these architectures that emphasize different parts of the problem, such as representation of polytopes, volume comparison between polytopes and volume prediction. Our results have varying rate of success depending on model and experimentation parameters. This work intends to start the discussion about applying machine learning techniques to computationally hard geometric problems.

2017

Experimental Study of the Ehrhart Interpolation Polytope

Vissarion Fisikopoulos, and Zafeirakis Zafeirakopoulos

In Mathematical Aspects of Computer and Information Sciences: 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings, Jun 2017

Abs

In this paper we define a family of polytopes called Ehrhart Interpolation Polytopes with respect to a given polytope and a parameter corresponding to the dilation of the polytope. We experimentally study the behavior of the number of lattice points in each member of the family, looking for a member with a single lattice point. That single lattice point is the h* vector of the given polytope. Our study is motivated by efficient algorithms for lattice point enumeration.

2015

Minkowski Decomposition and Geometric Predicates in Sparse Implicitization

Ioannis Z. Emiris, Christos Konaxis, and Zafeirakis Zafeirakopoulos

In Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation, Bath, UK, Jun 2015

Abs

Based on the computation of a polytope Q, called the predicted polytope, containing the Newton polytope P of the implicit equation, implicitization of a parametric hypersurface is reduced to computing the nullspace of a numeric matrix. Polytope Q may contain P as a Minkowski summand, thus jeopardizing the efficiency of sparse implicitization. Our contribution is twofold. On one hand we tackle the aforementioned issue in the case of 2D curves and 3D surfaces by Minkowski decomposing Q, thus detecting the Minkowski summand relevant to implicitization: we design and implement in Sage a new, public domain, practical, potentially generalizable and worst-case optimal algorithm for Minkowski decomposition in 3D based on integer linear programming. On the other hand, we formulate basic geometric predicates, namely membership and sidedness for given query points, as rank computations on the interpolation matrix, thus avoiding to expand the implicit polynomial. This approach is implemented in Maple

2009

Experimental evaluation and cross-benchmarking of univariate real solvers

Michael Hemmer, Elias P. Tsigaridas, Zafeirakis Zafeirakopoulos, Ioannis Z. Emiris, Menelaos I. Karavelas, and 1 more author

In Proceedings of the 2009 conference on Symbolic numeric computation, Kyoto, Japan, Jun 2009

Non-refereed proceedings

2016

On the space of Minkowski summands of a convex polytope

Ioannis Z. Emiris, Anna Karasoulou, Eleni Tzanaki, and Zafeirakis Zafeirakopoulos

, Lugano, Switzerland, Jun 2016

Abs PDF

We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage.

2013

A Gröbner Bases Method for Complementary Sequences

Christos Koukouvinos, Dimitris E Simos, and Zafeirakis Zafeirakopoulos

Jun 2013
Interpolation and Ehrhart Theory

Vissarion Fisikopoulos, Matthias Henze, and Zafeirakis Zafeirakopoulos

Jun 2013

Posters

2012

Partition Analysis via Polyhedral Geometry

Felix Breuer, and Zafeirakis Zafeirakopoulos

Sep 2012
Partition Analysis and Polyhedral Geometry

Zafeirakis Zafeirakopoulos

Sep 2012

2011

Using resultants for inductive Gröbner bases computation

Hamid Rahkooy, and Zafeirakis Zafeirakopoulos

Jul 2011
An algebraic framework for extending orthogonal designs

Christos Koukouvinos, Dimitris E. Simos, and Zafeirakis Zafeirakopoulos

Jul 2011

Technical Reports

2010

A Note on the Average Complexity Analysis of the Computation of Periodic and Aperiodic Ternary Complementary Pairs

Christos Koukouvinos, Veronika Pillwein, Dimitris E. Simos, and Zafeirakis Zafeirakopoulos

Oct 2010

2008

Cross-benchmarks of univariate algebraic kernels

Ioannis Emiris, Michael Hemmer, Menelaos Karavelas, Sebastian Limbach, Bernard Mourrain, and 2 more authors

Oct 2008

Theses

2012

Linear Diophantine Systems: Partition Analysis and Polyhedral Geometry

Zafeirakis Zafeirakopoulos

Johannes Kepler University, Dec 2012

2008

Study and Benchmarks for Real Root Isolation methods

Zafeirakis Zafeirakopoulos

Departments of Informatics and Telecommunication, Dec 2008

Unpublished

2013

On computing the elimination ideal using resultants with applications to Gröbner bases

Matteo Gallet, Hamid Rahkooy, and Zafeirakis Zafeirakopoulos

Dec 2013