Applied Mathematics

I. Infinite-Dimensional linear systems

Existence of solutions. We consider cone-constrained linear systems in Banach spaces, whose positive cone is induced by a partial ordering. We have provided a very general Farkas-like Theorem of the alternative which avoids the restrictive closedness assumption on the image of the cone by the linear mapping.

This permits to derive necessary and sufficient conditions for existence of solutions to many problems such as Volterra or Fredholm equations (with non-compact operators), the probabilistic Poisson equation, etc ... In the case of "Banach lattices", the conditions have an even simpler form.

Computational Aspects.    We consider a general linear programming problem in some Banach space and provide a (numerical) iterative scheme for computing the optimal value. We approximate the infinite-dimensional LP problem by a sequence of finite-dimensional LPs and prove (under weak assumptions) the asymptotic convergence of the corresponding sequence of optimal values to the optimal value of the original problem. We also prove that every accumulation point (in some appropriate weak topology) of the sequence of optimal solutions is an optimal solution of the original problem.

This also permits to derive a procedure for solving some linear equations, e.g. for computing the invariant probability of a Markov chain, for solving some linear partial diffential equations, etc ... To our knowledge, this is the first general computational scheme with such weak assumptions.
 
II. Homogeneous Numerical Integration (HNI). We consider the (computational) problem of integrating a continuous function on a polytope in Rn.  and more generally on domains whose boundary is defined by homogeneous functions. We have shown that integrating a homogeneous function reduces to integrating the same function on the boundary (e.g. faces of a polytope). Therefore by  iterating, integrating a polynomial on a polytope reduces to evaluations of the functions and its derivatives at the vertices only. It has been also extended to non convex polytopes. The HNI method (has been successfully implemented in numerical schemes for partial differential equations with sophisticated meshes and also in the well-known XFEM and NEM methods. For instance see the papers:

 

  • ``Numerical integration of homogeneous functions on convex and nonconvex polygons and polyhedra", by E. Chin, J.B. Lasserre, N. Sukumar, Comput. Mech. 56 (2015),  pp. 967--981.
  • ``Modeling crack discontinuities without element partitioning in the extended finite element method",  by E. Chin, J.B. Lasserre, N. Sukumar, Int. J. Num. Methods Eng. 110 (2017),  pp. 1201--1048.
  • "Attraction Controls the Inversion of Order by Disorder in Buckled Colloidal Monolayers", by Fabio Leoni and Yair Shokef, Phys. Rev. Lett. 118, 218002, 2017
  • "Fast Numerical Integration on Polytopic Meshes with Applications to Discontinuous Galerkin Finite Element Methods", by P.F. Antonietti, P. Houston, and G. Pennesi, J. Scientific Computing 77 (2018), pp. 1339--1370.
  • "Modeling curved interfaces without element‐partitioning in the extended finite element method" by E.B. Chin and N. Sukumar, Int. J. Numer. Methods in Eng. (2019)
  • "Extended virtual element method for the Laplace problem with singularities and discontinuities" by E. Benvenuti, A. Chiosi, G. Manzini, and N. Sukumar, in Computer Methods in Appl. Mech. Eng. 354, pp. 571--597 (2019)
  • "A line integral approach for the computation of the potential harmonic coefficients of a constant density polyhedron" by O. Jamet and D. Tsoulis, in Journal of Geodesy (2020)
  • ``Extended virtual element method for the torsion problem of cracked prismatic beams",  by Andrea Chiozzi & Elena Benvenuti, Meccanica 55, pp. 637--648, 2020
  • `An efficient method to integrate polynomials over polytopes and curved solides",  by E. B. Chin & N. Sukumar, Computer Aided Geometry Design 82, 2020
  • Spectral extended finite element method for band structure calculations in phononic crystals",  by E. B. Chin, A.A. Mokhtari, A. Srivastava, N. Sukumar, Journal of Computational Physics 427 (2021), 110066
  • High–order Discontinuous Galerkin Methods on Polyhedral Grids for Geophysical Applications: Seismic Wave Propagation and Fractured Reservoir Simulations, by Antonietti P.F., Facciolà C., Houston P., Mazzieri I., Pennesi G., Verani M. (2021) . In: Di Pietro D.A., Formaggia L., Masson R. (eds) Polyhedral Methods in Geosciences. SEMA SIMAI Springer Series, vol 27. Springer, Cham.
  • Minimizing numerical error in computing integrals on polynomial domains, by Fabian Gabor (2021). Annales Univ. Sci. Budapest, Section Comp. 52, pp. 109--129.
  • Robust high-order unfitted finite elements by interpolation-based discrete extension by S Badia, E Neiva and F Verdugo (2022), Computer & Mathematics with Applications 127, pp. 105--126.
  • NURBS enhanced virtual element methods for the spatial discretization of the multigroup neutron diffusion equation on curvilinear polygonal meshes by J.A. Ferguson, J. Kophasi, and M.D. Eaton (2022), J. Comput. Theor. Transport, 51(4), pp. 145--204.
  • Adaptive quadrature/cubature rule: Application to polytopes by B. Boroomand,  N. Niknejadi (2023), Comput. Methods Appl. Mech. Engrg, 403, 115726 (2023).
  • Evaluation of inner products of implicitly defined finite element functions on multiply connected planar mesh cells, by J.S. Ovall,  S.E Reynolds (2024), SIAM J. Sci. Computing 46(1), 10.1137/23M1569332

​We had already used a similar property to compute the volume of a polytope, with good performances. We have extended some of the previous results to arbitrary compact domains. We have also proposed another approach. We consider the result as a function of the right-hand-side and obtain a simple closed form expression of its Laplace transform. We then invert the latter by Cauchy residues techniques. For papers citing our work see the section ``Softwares".

 
III. Homogeneous functions. 

Legendre-Fenchel duality. We have shown that homogeneous functions play a special role with repect to the Legendre-Fenchel transform in "Convex Analysis". Indeed, the p-homgeneous functions are changed into q-homogeneous functions with 1/p+1/q=1. The same result is also true in other algebras for the corresponding transforms, e.g. the Bellman-Karush transform in the "min,+" algebra, the Laplace-transform in the "+,." algebra, the "min,max" transform in the "min,max" algebra.

A generalization of the Lowner-John ellipsoid. Given a compact set K (not necessarily convex) and "d" we consider the  problem of computing a set  "G" of the form {x: g(x)<= 1} that contains K, where "g" is a nonnegative and homogeneous polynomial of degree 2d, which is of minimum (Lebesgue) volume mong among all such sets. We show that it is a finite-dimensional convex problem with a unique solution, the higher-degree analogue of the celebrated Lowner-John ellipsoid in computational geometry. As for the latter we characterize the contacts points between G and K. In particular and quite surprisingly, the Lebesgue volume of G is a strictly convex function of the coefficient of "g". See 

An extension has been recently proposed in

 

IV. Singular Perturbation of Linear Operators. We are interested  in the singular perturbation of linear operators like the fundamental matrix of Markov chains, pseudo-inverse operators, Sylvester and Lyapunov equations, etc. The ultimate goal is to provide a simple procedure to get the Laurent series expansion in terms of the perturbation parameter. This Laurent series expansion provides insight on the bad behavior of the operator for small values of the parameter.

See for instance the paper Laurent series based RBF-FD method to avoid ill-conditioning.

  • P. Gonzalez-Rodriguez, V. Bayona and M. Moscoso. Engineering Analysis with Boundary Elements 52 (2015), pp. 24--31.

V. Discrete optimization and counting We are interested  in the problem of counting lattice points in a convex polytope with applications to discrete optimization. The idea is to use generating functions in the spirit of Brion and Vergne, Kantor, Sinai and Robins. We thus work in the space of "dual" variables associated with the nontrivial constraints that define the polytope; we then use the Z-transform (or generating function) of the function that counts the lattice points, considered as a function of the right-hand-side of the constraints. We then develop techniques to invert the Z-transform. We also use Brion and Vergne's periodic formula to derive a duality for integer programs, that parallels that of linear programming. In the same vein, we have also obtained a discrete Farkas lemma (for existence of a nonnegative integral solution to the linear system Ax=b) as well as an algebraic characterization of the integer hull of the covex rational polytope {Ax=b; x >=0}. All these contributions are reported in the book

 

VI. Inverse problems We are also interested in some Inverse Problems in Computational Geometry, Optimization, and Optimal Control, and show how they can be solved by the Moment-SOS Hierarchy. Namely:

- Reconstructing an unknown n-dimensional geometric object from the only knowledge of moments of a measure supported on this object. In particular we have shown how to recover the vertices of a polytope K from the sole knowledge of finitely many moments of the Lebesgue measure on K. Similarly, we can also recover the polynomial "g" that defines the boundary of the set G={x: g(x) <=1} from the sole knowledge of finitely many moments of the Lebesgue measure on G.

- Super-Resolution in signal processing, i.e., reconstructing a sparse signal (a signed atomic measure) from a few moments.

- Sparse interpolation (reconstructing a sparse polynomial from a few evaluations)

- Inverse optimization: Given a feasible solution "y" and a criterion "f" to minimize, find a criterion "g" as close as possible to "f" and such that "y" is a global optimizer for this new criterion.

- Inverse Optimal Control: Given a systems dynamics and a database of (trained) trajectories, find a Lagrangian for which those trajectories are optimal. This problem was motivated by an application in Humanoid Robotics where the goal is to understand human walk.

  • Pauwels E., Henrion D., Lasserre J.B. (2016) Linear Conic Optimization for Inverse Optimal Control,  SIAM J. Control & Optim. 54  pp. 1798--1825.