Volume and Integration

I have developed a (recursive) program to compute the exact volume of a convex polytope in Rn, given by its defining hyperplanes Ax<=b. The underlying method is based on Euler's identity for homogeneous functions. In the same vein we have also provided a method for integration of homogeneous functions on domains also defined by homogeneous functions. With E.S. Zeron (Mexico) we have also shown how to use Laplace Transform techniques to provide exact integration formula or very accurate approximations in several interesitng cases. For more details, see : 

  • J.B. Lasserre. An analytical expression and an algorithm for the volume of a convex polyhedron in Rn, J. Optim. Theor. Appl. 39 (1983), pp. 363--377. 
  • J.B. Lasserre. Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), pp. 2433--2441. 
  • J.B. Lasserre. Integration and homogeneous functions, Proc. Amer. Math. Soc. 127 (1999), pp. 813--818. 
  • J.B. Lasserre and K. Avrachenkov. The multi-dimensional version of \int[a,b] xp dx, Amer. Math. Monthly 108 (2001), pp. 151--154. 
  • J.B. Lasserre and E.S. Zeron Solving a class of multivariable integration problems via Laplace Lechniques Appl. Math. (Warsaw) 28 (2001), pp. 391--405.
  • J.B. Lasserre (2015) Volume of slices and sections of the simplex in closed form Optim. Letters 9, No 7,  pp. 1263----1269.

 

Our volume algorithm is one of those implemented in the public software VINCI. which itself the volume computation module of polymake, a tool for the algorithmic treatment of convex polyhedra, developed in the Discrete Geometry group at the Institute of Mathematics of Technische Universitat, Berlin. This volume computation occurs in various applications in Economics, computational complexity analysis, linear systems modeling, VLSI design, Statistics .... In particular, our volume algorithm (as well as our integration method for homogeneous functions) has also been used as a brick element in the "natural element method" (NEM), a relatively recent method for solving partial differential equations, as well as in recent extensions of finite element methods (X-FEM) for some boundary value problems involving discontinuities. In the X-FEM, the finite element mesh need not conform to the internal boundaries (cracks, material interfaces, voids, etc.), and hence a single mesh suffices for modeling as well as capturing the evolution of material interfaces and cracks in two- and three-dimensions. Our volume (and integration) algorithm is used in e.g.: 

  • A numerical method for solving partial differential equations on highly irregular grids, J. Braun and M. Sambridge, Nature 376 (1995), pp. 655-660. 
  • The natural element method in solid mechanics, N. Sukumar, B. Moran, and T. Belytschko, Int. J. Numer. Meth. Eng. 43 (1998), pp. 839--887. 
  • On entropy and clustering in earthquake hypocentre distributions, T. Nicholson, M. Sambridge, O. Gudmunsson. Geophys. J. Int. 142 (2000), 37--51. 
  • Computing the Information Content of Decoupled Designs, D.D Frey, E. Jahangir, F. Engelhardt. Research in Engineering Design 12 (2000), 90--102. 
  • Modelling three-dimensional piecewise homogeneous domains using the a-shape-based natural element method. E. Cueto, B. Calvo, M. Doblare. Int. J. Num. Meth. Eng. 54 (2002), 871--897. 
  • Overview and Recent Advances in Natural Neighbour Galerkin Methods E. Cueto, N. Sukumar, B. Calvo, M.A. Martinez, J. Cegonino, M. Doblare. Arch. Comput. Meth. Engng, 10 (2003), 307-384. 
  • Numerical integration in Natural Neighbour Galerkin methods, D. Gonzalez, E. Cueto, M.A. Martinez, M. Doblare. Int. J. Num. Meth. Eng. 60 (2004), 2077--2104. 
  • A study of the performance on natural neighbour-based Galerkin methods, I. Alfaro, J. Yonnet, F. Chinesta, E. Cueto. Int. J. Num. Meth. Eng. 71 (2007), 1436--1465. 
  • Application of the natural element method to finite deformation inelastic problems in isotropic and fiber-reinforced biological soft tissues, E. Pena, M.A. Martinez, B. Calvo, M. Doblare. Computer Methods in Applied Mechanics and Engineering 197 (2008), 1983--1996. 
  • Natural Neighbor Interpolation: Critical Assessment and New Contributions T. Bobach, PhD Thesis, University of Kaiserslautern, Germany, 2008. 
  • The Shape functions in the Natural Element Method based on Lasserre's algorithm. Jiang Tao, Qing Zhang, Mechanics in Enginering 30 (4),  79--83, (2008)
  • Numerical Integration of Polynomials and Discontinuous Functions on Irregular Convex Polygons and Polyhedrons S.E. Mousavi and N. Sukumar. Computational Mechanics 47 (2011), 535--554. 
  • Generalized Gaussian Quadrature Rules for Discontinuities and Crack Singularities in the Extended Finite Element Method S.E. Mousavi and N. Sukumar. Computer Methods in Applied Mechanics and Engineering 199 (2010), 3237--3249. 
  • Higher-order extended FEM for weak discontinuities -- level set representation, quadrature and application to magneto-mechanical problems, M. Kastner, S. Muller, J. Goldmann, C. Spieler, J. Brummund and V. Ulbricht. International Journal for Numerical Methods in Engineering 93 (2013), pp. 1403--1424. 
  • XFEM modeling and homogenization of magnetoactive composites, C. Spieler, M. Kastner, J. Goldmann, J. Brummund and V. Ulbricht. Acta Mechanica (August 2013). 
  • Natural element method for solving radiative transfer with or without conduction in three-dimensional complex geometries, Yong Zhang, Yu Ma, Hong-Liang Yi, and He-Ping Tan. Journal of Quantitative Spectroscopy & Radiative Transfer 129 (2013), pp. 118--130. 
  • On the numerical integration of trimmed isogeometric elements., A.P. Nagy and D.J. Benson. Comput. Methods Appl. Mech. Engrg. 284 (2015), 165--185. 
  • Fast numerical integration on polytopic meshes with applications to discontinuous Galerkin Finite Element Methods, P. F. Antonietti, P. Houston, G. Pennesi, J. Scientific Computing (2018).
  • A high-order discontinuous Galerkin method for level set problems on polygonal meshes, K. Lipnikov, N. Morgan, J. Comput. Physics (2019).
  • On probabilistic termination of functional programs with continuous distributions, R. Butner, L. Ong, J. , Proceedings of the 42nd ACM/SIGPLAN International Conference of Programming Language Design and Implementation, pp. 1312--1326, June 2021.
  • NURBS Enhanced Virtual Element Methods for the Spatial Discretization of the Multigroup Neutron Diffusion Equation on Curvilinear Polygonal Meshes, J.A. Ferguson, J. Kophazi, M.D. Eaton, J. Comput. Theor. Transport 51(4), pp. 145--204, 2022
  • Quadrature-free polytopic discontinuous Galerkin methods for transport problems, T.J. Radley, P. Houston, M.E. Hubbard, Mathematics in Engineering 6(1), pp. 192--220, 2024
  • Evaluation of inner products of implicitly defined finite element functions on multiply connected planar mesh cells, J.S. Ovall,  S.E Reynolds, SIAM J. Sci. Computing 46(1), 10.1137/23M1569332
and also in other various applications like e.g. 
 
  • Polyhedra in loop quantum gravity , E. Bianchi, P. Dona, S. Speziale. Physical Review D 83 (2011), 044035, and
  • Classical dynamics for  loop gravity , E. Aranguren, I. Garay, E.R. Livine, Physical Review D 105 (2022), 126024, and
  • Polytopes in all dimensional loop Quantum gravity, G. Long, Yongge Ma, Eur. Phys. J. C (2022) 82:41,  for reconstructing a polyhedron from the knowledge of faces' area and normals to the faces, and also in: 
  • Computing the information content of decoupled designs, D.D. Frey, E. Jahangir, F. Engelhardt. Research in Engineering Design 12 (2000), 90--102. 
  • Convex set symmetry using Blasche addition, H. Zouaki. Pattern Recognition 36 (2003), 753--763. 
  • Bayesian analysis of binary sequences, D.C. Torney. J. Comp. Appl. Math. 175 (2005), 231--243. 
  • Investigation of voxel warping and energy mapping approaches for fast 4D Monte Carlo dose calculations in deformed geometries using VMC++, E. Heath, F. Tessier, I. Kawrakow. Phys. Med. Biol. 56 (2011), 5187--5202. 
  • Pentahedral volume, chaos and quantum gravity, H.M. Haggard. Phys. Review D 87 (2013), 044020. 
  • A ``Helium atom" of space: Dynamical instability of the isochoric pentahedron, C.E. Coleman-Smith, B. Muller. Phys. Review D 87 (2013), 044047. 
  • An algorithm for approximating the highest density region in d-space, M.T. Waltman. Master thesis, Erasmus School of Economics, Rotterdam, The Netherlands, 2014 
  • Statistics of energy partitions for many-particle systems in arbitrary dimension, V. Aquilanti, Lombardi, M.B. Sevryuk. Regular and Chaotic Dynamics 19 (2014), 318--347. 
  • Efficient Voronoi volume estimation for DEM simulations of granular materials under confined conditions, G. Frenning. MethodsX 2 (2015), 79--90. 
  • Exact integration scheme for planewave-enriched partition of unity finite element method to solve the Helmholtz problem, S. Banerjee and S. Sukumar. Computer Methods in Appl. Mech. & Eng. (2017)  
  • A Neural Architecture for Bayesian Compressive Sensing over the Simplex via Laplace Techniques, S. Limmer and S. Stanczak, IEEE Transactions on Signal Processing (2018)

Also with my colleague E.S. Zeron (Math. Dept., INVESTAV-IPN, Mexico) we have provided an alternative algorithm, now based on (multivariate) inverse Laplace transform techniques. See :  J.B. Lasserre, E.S. Zeron. A Laplace transform algorithm for the volume of a convex polytope. Journal of the ACM 48 (2001), pp. 1126--1140.  

It has been used recently in e.g.: 

  • Time-Bounded Verification of CTMCs against Real-Time Specifications , T. Chen, M. Diciolla, M. Kwiatkowska, A Mereacre. In Formal Modeling and Analysis of Timed Systems, Lecture Notes in Computer Science Volume 6919, 2011, pp. 26-42 
  • Verification of linear duration properties over continuous-time markov chains, T. Chen, M. Diciolla, M. Kwiatkowska, A Mereacre. ACM Transactions on Computational Logic 14, No 4 (2013) art. 33 

As mentioned, we have also provided algorithms for integration of a polynomial (and more generally, homogeneous functions) on a convex polytope. In particular, our exact formula  J.B. Lasserre and K. Avrachenkov. The multi-dimensional version of \int[a,b] xpdx, Amer. Math. Monthly 108 (2001), pp. 151--154,  for integrating a polynomial on a Simplex has been proved very useful in Mesh Clustering; see e.g.: 

  • Mesh Clustering L_P-Centroidal Voronoi Tesselation and its Applications Fengtao Fan, F. Cheng, C. Huang, Y. Li, J. Wang, S. Lai., Proc. SIAM/ACM Joint Conference on Geometrical & Physical Modeling, San Francisco, 2009, pp. 301--306. 
  • L_P-Centroidal Voronoi Tesselation and its Applications B. Levy, Yang Liu. ACM Trans. Graphics 29, 4, Article 119. 
  • Gradient of the Objective Function for an Anisotropic Centroidal Voronoi Tessellation (CVT) - A revised, detailed derivation. G. Parigi, M. Piastra. arXiv:1408.5622v1, 2014, 

while our formula   J.B. Lasserre. Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), pp. 2433--2441,  has been recently used to provide efficient cubature formula on trimmed isogeometric elements of arbitrary shape as part of the standard finite element preprocessing step; see for instance: 

  • On the numerical integration of trimmed isogeometric elements. A.P. Nagy, D.J. Benson. Computer Methods in Applied Mechanics & Engineering 284, pp. 165--185, 2015. 
  • Anisotropic and feature sensitive triangular remeshing using normal lifting. V. Nivoliers, B. Levy, C. Geuzaine. J. Computational & Applied Mathematics, 2015 (doi:10.1016/j.cam.2015.01.041).
  • Fast numerical integration on polytopic meshes with applications to discontinuous Galerkin Finite Element Methods, P. F. Antonietti, P. Houston, G. Pennesi, J. Scientific Computing (2018).

More recently we  have also proposed an alternative formula for integration on the simplex

and we have also provided a numerical scheme to approximate the Lebesgue volume of compact semi-algebraic sets

Finally, combining the Laplace transform technique for integration in J.B. Lasserre and E.S. Zeron Solving a class of multivariable integration problems via Laplace Lechniques Appl. Math. (Warsaw) 28 (2001), pp. 391--405, with properties of D-finite functions, in

we have provided a very precise and efficient algorithm to compute probability of on-orbit collisions of satellites. This algorithm has been embedded and tested onboard of the ESOC-OPS-SAT3-Units CubSat Satellite via the CNES ASTERIA Software.