Normaliz

Its input data can be specified in terms of:

• a system of generators or vertices or
• a system of linear Diophantine equations, inequalities and congruences or
• a binomial ideal

Normaliz can be started from the command line or from the GUI interface jNormaliz (written by Vinicius Almendra and Bogdan Ichim). jNormaliz is included in the distribution. See the Normaliz documentation for details.

The user indicates the type of input data in the input file and controls the computation and the output via the GUI interface or command line options.

Normaliz is provided for two degrees of integer precision: 64 bits or infinite. For infinite precision it uses the GMP (Linux, Mac) and MPIR (Windows) libraries. Normaliz checks for overflows and switches to infinite precision if necessary.

Normaliz comes with interfaces for:

•  CoCoA,
•  GAP,
•  Macaulay2,
•  polymake,
•  Python and
•  Singular.

The Python interface (written by Sebastian Gutsche) PyNormaliz can be used in Python 2 and 3. The Macaulay2 interface (written by Gesa Kämpf) needs Macaulay2 1.1.99 or later. The Singular interface needs Singular 3-0-0 or later. Normaliz is used by B. Burton’s Regina. The access to Normaliz from SageMath is in preparation.

Normaliz is distributed under GPL.

You can contact the Normaliz team via:

• E-mail:  normaliz@uos.de
• Subscribe to our mailing list by sending an empty email to  normaliz-subscribe@list.serv.uos.de
• GitHub:  https://github.com/Normaliz

Please refer to Normaliz in any publication for which it has been used:

• W. Bruns, B. Ichim, C. Söger and U. von der Ohe: Normaliz. Algorithms for rational cones and affine monoids. Available at www.normaliz.uni-osnabrueck.de.

The corresponding \bibitem is:

• \bibitem W. Bruns, B. Ichim, C. S\”oger and U. von der Ohe: Normaliz. Algorithms for rational cones and affine monoids. Available at www.normaliz.uni-osnabrueck.de.

A BibTeX entry is:

• @Misc{Normaliz, author = {W. Bruns and B. Ichim and C. S\”oger and U. von der Ohe}, title = Normaliz. Algorithms for rational cones and affine monoids, howpublished ={Available at \texttt{https://www.normaliz.uni-osnabrueck.de}}}

• The first version of Normaliz was a C program developed by Winfried Bruns and Robert Koch in 1997/98. In 2002 Bruns added a Singular library. Witold Jarnicki improved the h-vector computation in 2003 and augmented the output options.
• Version 2.0 (of 2008) was completely rewritten in C++ by Bogdan Ichim. The algorithms and their implementations were significantly improved by the authors. Moreover, additional input modes and user-controlled arithmetic checks were added.
• From version 2.5 (2010) on Winfried Bruns and Christof Söger (until 2016) have developed Normaliz. In the versions 2.5 – 2.12 many new features were added, in particular inhomogeneous input. In version 2.7 the pyramid decomposition was introduced and in 2.8 it was efficiently parallelized.
• NmzIntegrate (2013) added weighted Ehrhart series and Lebesgue integrals of polynomials over rational polytopes. (Now included in Normaliz itself.)
• Version 3.0 (2015) introduced a new user interface (with backward compatibility), the automatic choice of integer arithmetic and several other improvements. Later on nonpointed cones and polyhedra without vertices were added.
• In 2016 – 2018 several new algorithms and computation goals were introduced. Matthias Köppe contributed autotools scripts, and Sebastian Gutsche wrote PyNormaliz. Together they allow the use of Normaliz from SageMath.
• Version 3.7.0 (2019) added algebraic polyhedra, i.e., polyhedra defined over real algebraic extensions of the rational numbers.
• Version 3.9.4 (2022) added semialgebraic constraints for lattice points
• Version 3.10.2 (2024) added special functions for fusion rings
• For further details see the file  CHANGELOG in the Normaliz distribution. The  Normaliz manual lists the changes in the most recent versions.

•  Winfried Bruns
•  Max Horn

Contributors

• Matthias Köppe

Previous Contributors and Team Members

• Sebastian Gutsche
• Bogdan Ichim
• Witold Jarnicki
• Gesa Kämpf
• Robert Koch
• Tim Römer
• Richard Sieg
• Christof Söger
• Ulrich von der Ohe

Reference Documentation:

• Normaliz:  Normaliz Manual
• PyNormaliz:  PyNormaliz Manual
• Normaliz:  Normaliz Short Reference
• jNormaliz:   jNormaliz1.7 Manual

Additional Material:

• For interesting and challenging examples for Normaliz see:  Examples
• For a list of papers with a reference to Normaliz see:  Publications

Interesting and challenging examples for Normaliz

Some interesting and challenging examples document the power of Normaliz. Please send examples that you would like to add to the collection to one of the authors!

Each example is provided as a separate zip file containing input and output. The mathematical background and more information is provided by the references specified. All examples have been computed with a pre-release version of Normaliz 3.1.1.

1.  nonICP: An example of a normal lattice polytope that has no unimodular cover and even violates the integral Carathéodory property [BG, Section 2.D], [BG2], [BGHMW].
2.  ICPnonUHC: An example of a lattice polytope satisfying ICP, but without unimodular cover [B].
3.  VeryampleNonNormal: An example of a non-normal very ample lattice polytope [BG1]. (See [BG, p. 87] for further examples.)
4.  dim3tight: A 3-dimensional tight cone [BG, Section 2.D].
5.  cube210: Ehrhart polynomial. The period of the Ehrhart quasipolynomial of a rational polytope divides the least common multiple of the denominators of the vertices. Usually one has equality, but there are exceptions. In particular there exist non-lattice polytopes whose Ehrhart quasipolynomial is a polynomial. We give a 3-dimensional example with the face lattice of the cube.
6.  NonNormal3polytope: A nonnormal rectangular simplex of dimension 3 [BG0].
7.  Magic: (Magic) squares of nonnegative integers for which all row and column sums and the two diagonal sums are equal.
8.  contingency: The missing cases in the Ohsugi-Hibi classification of normal monoids derived from contingency tables (4x4x3, 5x4x3, 5x5x3) and the first nonnormal case (6x4x3); see [OH], [BHIKS]. (Run with -N for Hilbert basis computation.)
9.  semigraphoid5: The semi-graphoid for N = 5 [HMSSW], [BHIKS]. (Run with -N for Hilbert basis computation.)
10.  cut_monoids: Verification of a conjecture of Sturmfels and Sullivant on normality of cut polytopes for some specific graphs [SS], [BHIKS], [O], [S].
11.  SturmfelsWelker: Two models of statistical ranking discussed in [SW], the inversion model for n = 6 (lo6) and the ascending model for n = 5 (bo5).
12.  VotingHilbertSeries: Some examples of Hilbert (or Ehrhart) series computations for elections with four candidates: the Condorcet paradox, the Condorcet efficiency of plurality voting, plurality voting vs. cutoff for 4 candidates. See [BS] and [BIS2] where some more models of voting theory are discussed. The computations use symmeztrization based on [BS]. The computations require Normaliz 3.6.0 or higher.
13.  VotingVolumes: Examples of volume computations for elections with four candidates, for which Hilbert series are out of reach or take very long: the strict Borda paradox [BIS] and “4 rules” [BI]. Also the three models from VotingHilbertSeries have been included with restriction to volume computation. The computations require Normaliz 3.6.0 or higher.
14.  Cyclotomic: Cyclotomic monoids; see [BeHo]. The computations just confirm a theorem of Beck and Hosten. The first open case of 105th roots of unity is not yet reachable.
15.  VanishingSums: The aim is to find all linear combinations of the n-th roots of unity with nonnegative integer coefficients that sum to 0. See for the [LL] mathematical background. The solution of the problem requires a Gilbert basis calculation.  This application of Normaliz was used for a project in mathematical music; see  http://www.dynamictonality.com/xronomorph.htm and [Mi]. We include input and output files for n=66,70,78, The first impossible case seems to be n=105. But Normaliz can compute the extreme rays in this case. Because of their large number, we list only the lexicographic largest component of each orbit under the group of rotations.
16.  CyclicPolytopes: The face numbers of cyclic polytopes attain the maximum set by the upper bound theorem (for example, see [BH]. We include two examples that show Normaliz’ power in computing convex hulls for polytopes defined by vertices with very large coordinates. (Suggested by D. Avis and Ch. Jordan.) The larger of the two examples requires a large amount of RAM (~ 60 GB).
17.  ClassicalPolyhedra: Classical polyhedra like the icosahedron and the dodecahedron require coordinates in subfields of the real numbers that are algebraic over the rational numbers. QNormaliz computes such polyhedra, and from version 3.7.0 on Normaliz itself will do it.
18.  PolytopeVolumes: This zip file contains input files for the computations on the paper Polytope volume by descent in the face lattice and applications in social choice by W. Bruns and B. Ichim. The input files for vinci are in the subdirectory vinci, those for Normaliz are distributed to several subdirectories. The file names are explained in the paper.
19.  Volume by the Lawrence algorithm: This file contains the input and result files of the volume computations in [BI2] by the Lawrence algorithm.
20.  FusionRings: This zip file contains two examples of input files for fusion ring computation. Normaliz has an own interface for fusion rings. See Appendix H of the Normaliz module. For the theory of fusion rings we refer to [EGNO].

References

• [BeHo] M. Beck and S. Hosten. Cyclotomic polytopes and growth series of cyclotomic lattices. Math. Res. Lett. 13 (2006), no. 4, 607–622.
• [BH] W. Bruns and J. Herzog. Cohen-Macaulay rings. Rev. ed. Cambridge University Press 1998.
• [B] W. Bruns. On the integral Carathéodory property. Experiment. Math. 16 (2007), no. 3, 359–365.
• [BG] W. Bruns and J. Gubeladze. Polytopes, rings, and K-theory. Springer Monographs in Mathematics, Springer, 2009.
• [BG0] W. Bruns and J. Gubeladze. Rectangular simplicial semigroups. In: D. Eisenbud (ed.), Commutative algebra, algebraic geometry, and computational methods, 201–213, Springer 1999.
• [BG1] W. Bruns and J. Gubeladze, Polytopal linear groups. J. Algebra 218 (1999), no. 2, 715–737.
• [BG2] W. Bruns and J. Gubeladze. Normality and covering properties of affine semigroups. J. Reine Angew. Math. 510 (1999), 161–178.
• [BGHMW] W. Bruns, J. Gubeladze, M. Henk, A. Martin, and R. Weismantel. A counterexample to an integer analogue of Carathéodory’s theorem. J. Reine Angew. Math. 510 (1999), 179–185.
• [BHIKS] W. Bruns, R. Hemmecke, B. Ichim, M. Köppe, and C. Söger. Challenging computations of Hilbert bases of cones associated with algebraic statistics. Exp. Math. 20 (2011), no. 1, 25–33.
• [BI] W. Bruns and B. Ichim. Polytope volume by descent in the face lattice and applications in social choice. Math. Program. Comput. 13 (2021), no. 2, 415–442.
• [BI2] W. Bruns and B. Ichim. Computations of volumes in five candidates elections. arXiv:2109.00473.
• [BIS] W.Bruns, B. Ichim and C. Söger. The power of pyramid decompositions in Normaliz. J. Symbolic Comput. 74 (2016), 513–536.
• [BIS2] W. Bruns, C. Söger and B. Ichim. Computations of volumes and Ehrhart series in four candidates elections. Ann. Oper. Res. 280 (2019), no. 1-2, 241–265.
• [BS] W.Bruns and C. Söger. The computation of generalized Ehrhart series in Normaliz. J. Symbolic Comput. 68 (2015), part 2, 75–86.
• [EGNO] P. Etingof, S. Gelaki, D. Nikshych, and V. Ostrik, Tensor Categories, American Mathematical Society, (2015).
• [HMSSW] R. Hemmecke, J. Morton, A. Shiu, B. Sturmfels, and O. Wienand. Three counter-examples on semi-graphoids. Combin. Probab. Comput. 17 (2008), no. 2, 239–257.
• [LL] T. Y. Lam and K. H. Leung. On vanishing sums of roots of unity. J. Algebra 224 (2000), 91–109.
• [Mil] A. J. Milne et al. XronoMorph: Algorithmic generation of perfectly balanced and well-formed rhythms. Use of Normaliz communicated by D. Bulger. Available at  http://www.nime.org/proceedings/2016/nime2016_paper0077.pdf.
• [O] H. Ohsugi. Normality of cut polytopes of graphs in a minor closed property. Discrete Math. 310 (2010), no. 6-7, 1160–1166.
• [OH] H. Ohsugi and T. Hibi. Toric ideals arising from contingency tables. In: R.V. Gurjar, S. A. Katre, R.A. Rao and J.K. Verma (ed.), Commutative algebra and combinatorics, Ramanujan Mathematical Society Lecture Notes Series 4, 91–115, Ramanujan Mathematical Society, 2007.
• [S] C. Söger. Parallel Algorithms for Rational Cones and Affine Monoids. Dissertation thesis (2014), urn:nbn:de:gbv:700-2014042212422.
• [SS] B. Sturmfels and S. Sullivant. Toric geometry of cuts and splits. Michigan Math. J. 57 (2008), 689–709.
• [SW] B. Sturmfels and V. Welker. Commutative Algebra of Statistical Ranking. J. Algebra 361 (2012), 264–286.

Here you find a list of papers citing Normaliz:

• Papers on Normaliz:  OnNormaliz
• Papers with references to Normaliz:  WithNormaliz

Legal disclaimer

• Normaliz (all versions) is free software licensed under the GNU General Public License, version 3. You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. See the  GNU General Public License for more details.
• It is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

All components of Normaliz mentioned below (except the jNormaliz source code) can be downloaded from:

 https://github.com/Normaliz/Normaliz/releases

See the manual for restrictions on some systems. For some older versions of Normaliz see:  All versions

Binary installation

1. Download the package for your operating system (Linux64, MacOS or Windows64).
2. Unzip it in a directory of your choice.
3. Within this directory you will then find a subdirectory normaliz-x.y.z, the Normaliz directory.
4. If you want to run Normaliz from the command line, it may be necessary to copy the executables normaliz(.exe) to a directory in your search path.

Note that jNormaliz, the Singular library and the Macaulay2 package are included in this distribution. They are contained in the Normaliz directory. The documentation is available in the subdirectory doc of the Normaliz directory.

Source installation

1. Download the package normaliz-x.y.z.zip (or tar.gz) and unzip it as described for the binary installation.
2. Build Normaliz as described in Section 11 of the manual (to be found in the subdirectory doc).

The source installation includes PyNormaliz, the Singular library and the Macaulay2 package, but jNormaliz is not contained in it.

Docker image

Normaliz is available as a Docker image; see

 https://hub.docker.com/r/normaliz/normaliz/

or just run “docker run -ti normaliz/normaliz” after the installation of Docker on your system.