Differences between revisions 14 and 32 (spanning 18 versions)
Revision 14 as of 2018-04-13 17:19:57
Size: 10132
Editor: jipilab
Comment:
Revision 32 as of 2020-03-08 13:41:55
Size: 14830
Editor: jipilab
Comment: Removed Release Notes to migrate to Trac wiki...
Deletions are marked like this. Additions are marked like this.
Line 9: Line 9:
 * Extend the polyhedral geometry component of sage  * Extend the polyhedral geometry component of Sage
Line 41: Line 41:
 * Test the algebraic polytopes [[https://trac.sagemath.org/ticket/25097|#25097]]
 * Make Polyhedron_normaliz accept algebraic stuff, related to [[https://trac.sagemath.org/ticket/25097|#25097]] (adapt _init_from_Hrepresentation)
 * Add known irrational polytope to the library of polytopes
 * repr of NumberFields (the parents) should indicate its embedding if there is one [[https://trac.sagemath.org/ticket/21161|#21161]] (this ticket will help in debugging and have good feedback)
Line 48: Line 44:
 * Make Ehrhart (quasi)polynomial accessible through normaliz (and consisten with the current one) [[https://trac.sagemath.org/ticket/18957|#18957]]
 * Adjust the new features of the normaliz backend to the latest version [[https://trac.sagemath.org/ticket/25091|#25091]] [[https://trac.sagemath.org/ticket/25090|#25090]]
 * Make Pynormaliz a feature in the PythonModule framework
 * Polymake: Turn polymake applications into objects with directories [[https://trac.sagemath.org/ticket/27736|#27736]]
 * Add Perles and irrational polytopes to library [[https://trac.sagemath.org/ticket/27728|#27728]]
 * Euclidean automorphisms group of polytopes in Normaliz
 * The integration of automorphisms into SageMath
 * The remaining main computation goal, Hilbert and Ehrhart series turned out to be a very difficult task since it would require the precise construction of a fundamental domain of the group action.
 * Once interactive H-representation in normaliz is possible ("redund-like") make it work with the "A & B" operation in Sage!
Line 53: Line 54:
=== August 2019 ===

Here are improvements realized up to the Sage Days 100 in Bonn

==== Sage ====

The following are quite advanced and many are under review:

 * Implement is_pyramid, is_bipyramid, is_prism for polytopes [[https://trac.sagemath.org/ticket/27689|#27689]]
 * Implement wedge over a face of Polyhedron [[https://trac.sagemath.org/ticket/27973|#27973]]
 * Implement center of a HyperplaneArrangement [[https://trac.sagemath.org/ticket/28245|#28245]]
 * Normal cone of faces of polyhedra [[https://trac.sagemath.org/ticket/17215|#17215]]
 * Implement facets method for Polyhedron [[https://trac.sagemath.org/ticket/27974|#27974]]
 * ehrhart_polynomial should be made available for polytopes defined over QQ [[https://trac.sagemath.org/ticket/18957|#18957]]

 * Fixed: bug in polyhedron over RDF [[https://trac.sagemath.org/ticket/24877|#24877]]
 * Fixed: Make outer normal fans readily available [[https://trac.sagemath.org/ticket/27993|#27993]]
 * Fixed: py3: polyhedron folder with optional packages [[https://trac.sagemath.org/ticket/28235|#28235]]
 * Fixed: Move rational methods of the backend normaliz to the `_QQ` class [[https://trac.sagemath.org/ticket/28240|#28240]]
 * Fixed: add .is_self_dual method for polytopes [[https://trac.sagemath.org/ticket/28256|#28256]]
 * Fixed: Add .boundary_complex() method for simplicial polytopes [[https://trac.sagemath.org/ticket/28248|#28248]]
 * Fixed: repr of NumberFields (the parents) should indicate its embedding if there is one [[https://trac.sagemath.org/ticket/21161|#21161]]

The following tickets have been created and should be worked on:

 * Thematic Tutorial on algebraic polytopes in Sage using Normaliz [[https://trac.sagemath.org/ticket/28230|#28230]]
 * Add the 0/1-hypercube to the library of polytopes [[https://trac.sagemath.org/ticket/28247|#28247]]

=== April/May 2019 ===

Here are improvements realized during the Research in Pairs at MFO

==== Sage ====

The following are quite advanced and many are under review:

 * upgrade normaliz to 3.7.2, pynormaliz to 2.5 [[https://trac.sagemath.org/ticket/27731|#27731]]
 * Almost done with repr of NumberFields (the parents) should indicate its embedding if there is one [[https://trac.sagemath.org/ticket/21161|#21161]]
 * Adjust the new features of the normaliz backend to the latest version [[https://trac.sagemath.org/ticket/25091|#25091]]
 * Algebraic polytopes now under review [[https://trac.sagemath.org/ticket/25097|#25097]]
 * Add the H4 polytopes and generalized permutahedron to the library of polytopes [[https://trac.sagemath.org/ticket/27760|#27760]]
 * Create a variant of the polymake interface using polymake's callable library (polymake::Main) via JuPyMake [[https://trac.sagemath.org/ticket/22704|#22704]]
 * Add Perles and irrational polytopes to library [[https://trac.sagemath.org/ticket/27728|#27728]]

 * Fixed: Upgrade polymake to version 3.4 (current interface breaks) [[https://trac.sagemath.org/ticket/24905|#24905]]
 * Fixed: upgrade normaliz to 3.7.1, pynormaliz to 2.1 and package e-antic [[https://trac.sagemath.org/ticket/27682|#27682]]
 * Fixed: Refactor backend_normaliz [[https://trac.sagemath.org/ticket/27716|#27716]]
 * Fixed: Polytope snub_cube should allow exact coordinates [[https://trac.sagemath.org/ticket/26340|#26340]]
 * Fixed: number_field_elements_from_algebraics should create embedded number field elements [[https://trac.sagemath.org/ticket/20181|#20181]]
 * Fixed: The attribute _vector of H and V representation is exposed [[https://trac.sagemath.org/ticket/27709|#27709]]
 * Fixed: Remove old deprecation warning of Minkowski -> minkowski [[https://trac.sagemath.org/ticket/27722|#27722]]
 * Fixed: Upgrade LiDIA to v2.3.0+latte-patches-2019-05-01 [[https://trac.sagemath.org/ticket/27746|#27746]]
 * Fixed: PolymakeElement._sage_: Handle polymake type Polyhedron [[https://trac.sagemath.org/ticket/27742|#27742]]

==== PyNormaliz ====

 * Update PyQNormaliz by adding lattice points, integer hull and volume
 * Removal of instabilities (Memory corruption etc.)
 * Added functions
 * Added test framework
 * Interfacing the new Normaliz features
 * Adjustment for Sage signal handling
 * Several improvements to JuPyMake
 * Test implementation of polymake interface for python in cython
 * Alpha implementation of Normaliz.jl, a julia interface to Normaliz, to be used in OSCAR and GAP.

==== Normaliz ====

 * Inclusion of the computation of automorphism groups for general polytopes and cones, also for algebraic polytopes and cones.
 * Various types of automorphism groups can be computed: combinatorial, rational, integral and (for algebraic data) algebraic.
 * Efficient exploitation of the automorphism group in polyhedral computations has been realized for volumes, Hilbert bases and lattice points in polytopes.
 * Three new releases of Normaliz, namely 3.7.1, 3.7.2 and 3,7.3, that have repared several small bugs and improved weak points.
 * The API libnormaliz has been restructured and enriched by the accessibility of the output function.
Line 57: Line 132:
Here are improvements realized during the Coding Sprints at the IMA to objects related to polyhedron in Sage:

 * Thematic tutorial on polyhedron in Sage [[https://trac.sagemath.org/ticket/22572|#22572]]
Here are improvements realized during the Coding Sprints at the IMA in Minneapolis to objects related to polyhedron in Sage:
Line 63: Line 137:
 * Change error message in construction of polyhedron object [[https://trac.sagemath.org/ticket/24835|#24835]]
Line 65: Line 138:
 * Implement stacking onto a face of a polyhedron [[https://trac.sagemath.org/ticket/24847|#24847]]
 * Implement join of polytopes [[https://trac.sagemath.org/ticket/24848|#24848]]
 * Implement one point suspension and face split of polyhedron [[https://trac.sagemath.org/ticket/24886|#24886]]
 * The polar of a polyhedron should carry the backend used [[https://trac.sagemath.org/ticket/25081|#25081]]
Line 71: Line 140:
 * Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. Now Positive review. [[https://trac.sagemath.org/ticket/22984|#22984]]
Line 74: Line 142:
 * Fixed: Change error message in construction of polyhedron object [[https://trac.sagemath.org/ticket/24835|#24835]]
 * Fixed: Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. [[https://trac.sagemath.org/ticket/22984|#22984]]
 * Fixed: Thematic tutorial on polyhedron in Sage [[https://trac.sagemath.org/ticket/22572|#22572]]
 * Fixed: Implement stacking onto a face of a polyhedron [[https://trac.sagemath.org/ticket/24847|#24847]]
 * Fixed: Implement join of polytopes [[https://trac.sagemath.org/ticket/24848|#24848]]
 * Fixed: Implement one point suspension and face split of polyhedron [[https://trac.sagemath.org/ticket/24886|#24886]]
 * Fixed: The polar of a polyhedron should carry the backend used [[https://trac.sagemath.org/ticket/25081|#25081]]

Line 78: Line 155:
 * Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 [[https://trac.sagemath.org/ticket/22984|#22984]]: repair of performance loss
Line 80: Line 156:
 * Algebraic polytopes in Qnormaliz using e-antic [[https://trac.sagemath.org/ticket/25097|#25097]]: convex hull computation completed, improvement of Qnormaliz input and output, control of interrupts and parallelization via libQnormaliz  * Algebraic polytopes in Qnormaliz using e-antic [[https://trac.sagemath.org/ticket/25097|#25097]]: convex hull computation completed, improvement of Qnormaliz input and output, control of interrupts and parallelization via libQnormaliz, lattice points, integer hull and volume added. Qnormaliz should be essentially complete now.
 * General getters for cone properties. The getters can be used in future interfaces to make access to Normaliz cone properties easier
 * resetGrading method for cone: Can be used to replace the grading and redo certain Normaliz computation without having to delete
  degree indepenent properties, such as hilbert bases.
 * documentation of QNormaliz written
 * extensive tests of QNormaliz
 * link from libQnormaliz to libnormaliz in preparation for lattice point computation in algebraic polytopes
 * further attempts to improve QNormaliz output (not yet complete)
 * work on the C++ wrapper of e-antic


 * fixed: Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 [[https://trac.sagemath.org/ticket/22984|#22984]]: repair of performance loss
Line 83: Line 170:
 * Unified getter [[https://github.com/Normaliz/Normaliz/pull/182]]available for interfaces (return of results by type instead of computation goal)  * fixed: Normaliz 3.5.4 released
Line 90: Line 177:
 * Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 [[https://trac.sagemath.org/ticket/22984|#22984]] PyNormaliz (last version is 1.17):

 * All computation goals and output properties from Normaliz 3.5.4 are supported
 * It is possible to give functions RationalHandler, VectorHandler, and MatrixHandler to NmzResult to construct rationals, vectors, and matrices
 * Some documentation in the sources of NormalizModule.cpp
 * Functionality to copy cone
 * Functionality to reset grading of a cone in PyNormaliz

PyQNormaliz (current beta is 0.2, not available on PIPy):

 * All QNormaliz compute targets can be accessed
 * Input of number_field data as string
 * Input of number_field elements as list of 2-tuples, or as string
 * Ouput handlers RationalHandler, NumberfieldElementHandler, VectorHandler, and MatrixHandler
 * See example worksheet: https://nbviewer.jupyter.org/github/sebasguts/PyQNormaliz/blob/master/examples/Dodecahedron.ipynb

Line 94: Line 197:
Line 107: Line 211:
 * Upgrade polymake to version 3.2r2 (current interface breaks) [[https://trac.sagemath.org/ticket/24905|#24905]]


=== Sage 8.2 ===

 * Improvements:
   * Library of polytopes accepts a backend parameter
   * Fixed _facet_adjacency_matrix of non-full-dim. polyhedron
   * Optimize count lattice points of polytopes
    
 * New methods for polyhedron:
   * get_integral_point

=== Sage 8.1 ===

 * Improvements:
   * Fixed equation handling in .to_linear_program and integral_points_count
   * Fixed sage_input to include the backend used
   * Improved the polyhedron constructor
   * Fixed .affine_hull() raising an assertion error
   * Volume function handling better the different measures depending on the engine used

=== Sage 8.0 ===

Here is a sample of changes related to Polyhedral Geometry in this release.

 * Highlights:
   * Integration with Latte (function .integrate() )
   * New class for Voronoi Diagrams
   * Backend polymake for polyhedron

 * Improvements:
   * Fixed CartesianProduct with distinct dimensions
   * Fixed an error in .is_lattice_polytope()
   * Fixed overflow in integral_points()
   * Fixed normaliz backend with empty polyhedron

 * New methods for Polyhedron:
   * integral_points_count()

=== Sage 7.6 ===

Here is a sample of changes related to Polyhedral Geometry in this release:

 * Improvements:
   * documentation of Combinatorial and Discrete Geometry
   * combinatorial_automorphism_group
   * Fixes on .volume()
   * Fixes in integral_points()

 * New methods for Polyhedron:
   * .is_inscribed()
   * .neighborliness()
   * .is_neighborly()
   * .normal_fan()
   * .face_fan()
   * .is_combinatorially_isomorphic()
   * .face_truncation()

 * New methods for SimplicialComplexes:
   * star of a face
   * stellar subdivision

 * Generic interface to latte integrale:
   * count points
 * Upgrade polymake to version 3.4 (current interface breaks) [[https://trac.sagemath.org/ticket/24905|#24905]]
Line 176: Line 216:

 * Bensolve:
   * http://bensolve.org/

A Roadmap for Optimization and Polyhedral Geometry softwares interactions

(around Sage, (PyQ)Normaliz, SCIP, e-antic, Polymake, and others)

This page is intended to describe the current status of development of Sage related to optimization and polyhedral geometry.

Future & Current Projects

  • Extend the usage of Normaliz in Sage
  • Extend the polyhedral geometry component of Sage
  • Polyhedral arrangements and complexes

Meetings

Sage Days 84 on Polytopes in Olot

Tickets

Here are some practical lists of tickets:

Tickets from the Sage Days 84 March 2017

Tickets from the IMA Coding Sprint - April 2018

Tickets with keyword polytope

Current tickets of the Geometry component

Meta-tickets

There are already a few meta-tickets related to this topic:

To do

  • Thematic Tutorial for Py(Q)Normaliz installation/Usage in Sage
  • Increase documentation in Py(Q)Normaliz
  • Deprecate the opacity argument for plot3d and use alpha #21984

  • Make Pynormaliz a feature in the PythonModule framework

  • Polymake: Turn polymake applications into objects with directories #27736

  • Add Perles and irrational polytopes to library #27728

  • Euclidean automorphisms group of polytopes in Normaliz
  • The integration of automorphisms into SageMath

  • The remaining main computation goal, Hilbert and Ehrhart series turned out to be a very difficult task since it would require the precise construction of a fundamental domain of the group action.
  • Once interactive H-representation in normaliz is possible ("redund-like") make it work with the "A & B" operation in Sage!

Progress Report Timeline

August 2019

Here are improvements realized up to the Sage Days 100 in Bonn

Sage

The following are quite advanced and many are under review:

  • Implement is_pyramid, is_bipyramid, is_prism for polytopes #27689

  • Implement wedge over a face of Polyhedron #27973

  • Implement center of a HyperplaneArrangement #28245

  • Normal cone of faces of polyhedra #17215

  • Implement facets method for Polyhedron #27974

  • ehrhart_polynomial should be made available for polytopes defined over QQ #18957

  • Fixed: bug in polyhedron over RDF #24877

  • Fixed: Make outer normal fans readily available #27993

  • Fixed: py3: polyhedron folder with optional packages #28235

  • Fixed: Move rational methods of the backend normaliz to the _QQ class #28240

  • Fixed: add .is_self_dual method for polytopes #28256

  • Fixed: Add .boundary_complex() method for simplicial polytopes #28248

  • Fixed: repr of NumberFields (the parents) should indicate its embedding if there is one #21161

The following tickets have been created and should be worked on:

  • Thematic Tutorial on algebraic polytopes in Sage using Normaliz #28230

  • Add the 0/1-hypercube to the library of polytopes #28247

April/May 2019

Here are improvements realized during the Research in Pairs at MFO

Sage

The following are quite advanced and many are under review:

  • upgrade normaliz to 3.7.2, pynormaliz to 2.5 #27731

  • Almost done with repr of NumberFields (the parents) should indicate its embedding if there is one #21161

  • Adjust the new features of the normaliz backend to the latest version #25091

  • Algebraic polytopes now under review #25097

  • Add the H4 polytopes and generalized permutahedron to the library of polytopes #27760

  • Create a variant of the polymake interface using polymake's callable library (polymake::Main) via JuPyMake #22704

  • Add Perles and irrational polytopes to library #27728

  • Fixed: Upgrade polymake to version 3.4 (current interface breaks) #24905

  • Fixed: upgrade normaliz to 3.7.1, pynormaliz to 2.1 and package e-antic #27682

  • Fixed: Refactor backend_normaliz #27716

  • Fixed: Polytope snub_cube should allow exact coordinates #26340

  • Fixed: number_field_elements_from_algebraics should create embedded number field elements #20181

  • Fixed: The attribute _vector of H and V representation is exposed #27709

  • Fixed: Remove old deprecation warning of Minkowski -> minkowski #27722

  • Fixed: Upgrade LiDIA to v2.3.0+latte-patches-2019-05-01 #27746

  • Fixed: PolymakeElement._sage_: Handle polymake type Polyhedron #27742

PyNormaliz

  • Update PyQNormaliz by adding lattice points, integer hull and volume
  • Removal of instabilities (Memory corruption etc.)
  • Added functions
  • Added test framework
  • Interfacing the new Normaliz features
  • Adjustment for Sage signal handling
  • Several improvements to JuPyMake

  • Test implementation of polymake interface for python in cython
  • Alpha implementation of Normaliz.jl, a julia interface to Normaliz, to be used in OSCAR and GAP.

Normaliz

  • Inclusion of the computation of automorphism groups for general polytopes and cones, also for algebraic polytopes and cones.
  • Various types of automorphism groups can be computed: combinatorial, rational, integral and (for algebraic data) algebraic.
  • Efficient exploitation of the automorphism group in polyhedral computations has been realized for volumes, Hilbert bases and lattice points in polytopes.
  • Three new releases of Normaliz, namely 3.7.1, 3.7.2 and 3,7.3, that have repared several small bugs and improved weak points.
  • The API libnormaliz has been restructured and enriched by the accessibility of the output function.

April 2018

Sage

Here are improvements realized during the Coding Sprints at the IMA in Minneapolis to objects related to polyhedron in Sage:

  • Make features of normaliz accessible #25091

  • number_field_elements_from_algebraics should create embedded number field elements #20181 Sage-devel discussion

  • Helper functions and improvements in the normaliz backend #25097

  • Improve the output of repr_pretty for Polyhedron #24837

  • Construct RationalPolyhedralFan from possibly overlapping cones #25122

  • polygon3d ignores the "alpha" (and equivalent "opacity") argument #25095

  • PolyhedralComplex: preliminary implementation, see #20877

  • Fixed: Change error message in construction of polyhedron object #24835

  • Fixed: Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. #22984

  • Fixed: Thematic tutorial on polyhedron in Sage #22572

  • Fixed: Implement stacking onto a face of a polyhedron #24847

  • Fixed: Implement join of polytopes #24848

  • Fixed: Implement one point suspension and face split of polyhedron #24886

  • Fixed: The polar of a polyhedron should carry the backend used #25081

(Q)Normaliz

http://normaliz.uni-osnabrueck.de

  • Upgrade normaliz to 3.5.4 and pynormaliz to 1.16 #25090: Ehrhart series and triangulation of polytope also for inhomogeneous input

  • Algebraic polytopes in Qnormaliz using e-antic #25097: convex hull computation completed, improvement of Qnormaliz input and output, control of interrupts and parallelization via libQnormaliz, lattice points, integer hull and volume added. Qnormaliz should be essentially complete now.

  • General getters for cone properties. The getters can be used in future interfaces to make access to Normaliz cone properties easier
  • resetGrading method for cone: Can be used to replace the grading and redo certain Normaliz computation without having to delete
    • degree indepenent properties, such as hilbert bases.
  • documentation of QNormaliz written
  • extensive tests of QNormaliz
  • link from libQnormaliz to libnormaliz in preparation for lattice point computation in algebraic polytopes
  • further attempts to improve QNormaliz output (not yet complete)
  • work on the C++ wrapper of e-antic
  • fixed: Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 #22984: repair of performance loss

  • fixed: getProjectionCone might segfault https://github.com/Normaliz/Normaliz/issues/180

  • fixed: BadInputException for ProjectCone https://github.com/Normaliz/Normaliz/issues/181

  • fixed: Normaliz 3.5.4 released

Py(Q)Normaliz

https://pypi.python.org/pypi/PyNormaliz https://github.com/Normaliz/PyNormaliz

PyNormaliz (last version is 1.17):

PyQNormaliz (current beta is 0.2, not available on PIPy):

PyScipOpt

https://github.com/SCIP-Interfaces/PySCIPOpt

Sage devel discussion

  • Upgrade scipoptsuite to 5.0.1 #24662

  • Add SCIP backend using PySCIPOpt #21003

Polymake

https://polymake.org/doku.php

  • Upgrade polymake to version 3.4 (current interface breaks) #24905

A list of other Polyhedral Geometry softwares

What are other softwares dealing with polyhedral geometry? Here is a non-exhaustive list.

OptiPolyGeom (last edited 2022-04-18 03:44:30 by mkoeppe)