Efficient Approximation of Optimal TransportationMap by Pogorelov Map
Optimal transportation (OT) finds the most economical way to transport one measure to another and plays an important role in geometric modeling and processing. Based on the Brenier theorem, the OT problem is equivalent to the Alexandrov problem, which is the dual to the Pogorelov problem. Although solving the Alexandrov/Pogorelov problem are both equivalent to solving the Monge-Amp\{e}re equation, the former requires second type boundary condition and the latter requires much simpler Dirichlet boundary condition. Hence, we propose to use the Pogorelov map to approximate the OT map. The Pogorelov problem can be solved by a convex geometric optimization framework, in which we need to ensure the searching inside the admissible space. In this work, we prove the discrete Alexandrov maximum principle, which gives an apriori estimate of the searching. Our experimental results demonstrate that the Pogorelov map does approximate the OT map well with much more efficient computation.  more » « less
Award ID(s):
NSF-PAR ID:
10291683
Author(s) / Creator(s):
; ; ; ; ; ;
Date Published:
Journal Name:
Proceedings of International Meshing Roundtable
Format(s):
Medium: X
National Science Foundation
##### More Like this
1. (Ed.)
An optimal transportation map finds the most economical way to transport one probability measure to the other. It has been applied in a broad range of applications in vision, deep learning and medical images. By Brenier theory, computing the optimal transport map is equivalent to solving a Monge-Amp\ere equation. Due to the highly non-linear nature, the computation of optimal transportation maps in large scale is very challenging. This work proposes a simple but powerful method, the FFT-OT algorithm, to tackle this difficulty based on three key ideas. First, solving Monge-Amp\ere equation is converted to a fixed point problem; Second, the obliqueness property of optimal transportation maps are reformulated as Neumann boundary conditions on rectangular domains; Third, FFT is applied in each iteration to solve a Poisson equation in order to improve the efficiency. Experiments on surfaces captured from 3D scanning and reconstructed from medical imaging are conducted, and compared with other existing methods. Our experimental results show that the proposed FFT-OT algorithm is simple, general and scalable with high efficiency and accuracy.
more » « less
2. (Ed.)
Optimal transportation finds the most economical way to transport one probability measure to another, and it plays an important role in geometric modeling and processing. In this paper, we propose a moving mesh method to generate adaptive meshes by optimal transport. Given an initial mesh and a scalar density function defined on the mesh domain, our method will redistribute the mesh nodes such that they are adapted to the density function. Based on the Brenier theorem, solving an optimal transportation problem is reduced to solving a Monge-Amp\ere equation, which is difficult to compute due to the high non-linearity. On the other hand, the optimal transportation problem is equivalent to the Alexandrov problem, which can finally induce an effective variational algorithm. Experiments show that our proposed method finds the adaptive mesh quickly and efficiently.
more » « less
3. Embedding properties of network realizations of dissipative reduced order models Jörn Zimmerling, Mikhail Zaslavsky,Rob Remis, Shasri Moskow, Alexander Mamonov, Murthy Guddati, Vladimir Druskin, and Liliana Borcea Mathematical Sciences Department, Worcester Polytechnic Institute https://www.wpi.edu/people/vdruskin Abstract Realizations of reduced order models of passive SISO or MIMO LTI problems can be transformed to tridiagonal and block-tridiagonal forms, respectively, via dierent modications of the Lanczos algorithm. Generally, such realizations can be interpreted as ladder resistor-capacitor-inductor (RCL) networks. They gave rise to network syntheses in the rst half of the 20th century that was at the base of modern electronics design and consecutively to MOR that tremendously impacted many areas of engineering (electrical, mechanical, aerospace, etc.) by enabling ecient compression of the underlining dynamical systems. In his seminal 1950s works Krein realized that in addition to their compressing properties, network realizations can be used to embed the data back into the state space of the underlying continuum problems. In more recent works of the authors Krein's ideas gave rise to so-called nite-dierence Gaussian quadrature rules (FDGQR), allowing to approximately map the ROM state-space representation to its full order continuum counterpart on a judicially chosen grid. Thus, the state variables can be accessed directly from the transfer function without solving the full problem and even explicit knowledge of the PDE coecients in the interior, i.e., the FDGQR directly learns" the problem from its transfer function. This embedding property found applications in PDE solvers, inverse problems and unsupervised machine learning. Here we show a generalization of this approach to dissipative PDE problems, e.g., electromagnetic and acoustic wave propagation in lossy dispersive media. Potential applications include solution of inverse scattering problems in dispersive media, such as seismic exploration, radars and sonars. To x the idea, we consider a passive irreducible SISO ROM fn(s) = Xn j=1 yi s + σj , (62) assuming that all complex terms in (62) come in conjugate pairs. We will seek ladder realization of (62) as rjuj + vj − vj−1 = −shˆjuj , uj+1 − uj + ˆrj vj = −shj vj , (63) for j = 0, . . . , n with boundary conditions un+1 = 0, v1 = −1, and 4n real parameters hi, hˆi, ri and rˆi, i = 1, . . . , n, that can be considered, respectively, as the equivalent discrete inductances, capacitors and also primary and dual conductors. Alternatively, they can be viewed as respectively masses, spring stiness, primary and dual dampers of a mechanical string. Reordering variables would bring (63) into tridiagonal form, so from the spectral measure given by (62 ) the coecients of (63) can be obtained via a non-symmetric Lanczos algorithm written in J-symmetric form and fn(s) can be equivalently computed as fn(s) = u1. The cases considered in the original FDGQR correspond to either (i) real y, θ or (ii) real y and imaginary θ. Both cases are covered by the Stieltjes theorem, that yields in case (i) real positive h, hˆ and trivial r, rˆ, and in case (ii) real positive h,r and trivial hˆ,rˆ. This result allowed us a simple interpretation of (62) as the staggered nite-dierence approximation of the underlying PDE problem [2]. For PDEs in more than one variables (including topologically rich data-manifolds), a nite-dierence interpretation is obtained via a MIMO extensions in block form, e.g., [4, 3]. The main diculty of extending this approach to general passive problems is that the Stieltjes theory is no longer applicable. Moreover, the tridiagonal realization of a passive ROM transfer function (62) via the ladder network (63) cannot always be obtained in port-Hamiltonian form, i.e., the equivalent primary and dual conductors may change sign [1]. 100 Embedding of the Stieltjes problems, e.g., the case (i) was done by mapping h and hˆ into values of acoustic (or electromagnetic) impedance at grid cells, that required a special coordinate stretching (known as travel time coordinate transform) for continuous problems. Likewise, to circumvent possible non-positivity of conductors for the non-Stieltjes case, we introduce an additional complex s-dependent coordinate stretching, vanishing as s → ∞ [1]. This stretching applied in the discrete setting induces a diagonal factorization, removes oscillating coecients, and leads to an accurate embedding for moderate variations of the coecients of the continuum problems, i.e., it maps discrete coecients onto the values of their continuum counterparts. Not only does this embedding yields an approximate linear algebraic algorithm for the solution of the inverse problems for dissipative PDEs, it also leads to new insight into the properties of their ROM realizations. We will also discuss another approach to embedding, based on Krein-Nudelman theory [5], that results in special data-driven adaptive grids. References [1] Borcea, Liliana and Druskin, Vladimir and Zimmerling, Jörn, A reduced order model approach to inverse scattering in lossy layered media, Journal of Scientic Computing, V. 89, N1, pp. 136,2021 [2] Druskin, Vladimir and Knizhnerman, Leonid, Gaussian spectral rules for the three-point second dierences: I. A two-point positive denite problem in a semi-innite domain, SIAM Journal on Numerical Analysis, V. 37, N 2, pp.403422, 1999 [3] Druskin, Vladimir and Mamonov, Alexander V and Zaslavsky, Mikhail, Distance preserving model order reduction of graph-Laplacians and cluster analysis, Druskin, Vladimir and Mamonov, Alexander V and Zaslavsky, Mikhail, Journal of Scientic Computing, V. 90, N 1, pp 130, 2022 [4] Druskin, Vladimir and Moskow, Shari and Zaslavsky, Mikhail LippmannSchwingerLanczos algorithm for inverse scattering problems, Inverse Problems, V. 37, N. 7, 2021, [5] Mark Adolfovich Nudelman The Krein String and Characteristic Functions of Maximal Dissipative Operators, Journal of Mathematical Sciences, 2004, V 124, pp 49184934 Go back to Plenary Speakers Go back to Speakers Go back
more » « less
4. (Ed.)
Over the past two decades, educators have used computer-supported collaborative learning (CSCL) to integrate technology with pedagogy to improve student engagement and learning outcomes. Researchers have also explored the diverse affordances of CSCL, its contributions to engineering instruction, and its effectiveness in K-12 STEM education. However, the question of how students use CSCL resources in undergraduate engineering classrooms remains largely unexplored. This study examines the affordances of a CSCL environment utilized in a sophomore dynamics course with particular attention given to the undergraduate engineering students’ use of various CSCL resources. The resources include a course lecturebook, instructor office hours, a teaching assistant help room, online discussion board, peer collaboration, and demonstration videos. This qualitative study uses semi-structured interview data collected from nine mechanical engineering students (four women and five men) who were enrolled in a dynamics course at a large public research university in Eastern Canada. The interviews focused on the individual student’s perceptions of the school, faculty, students, engineering courses, and implemented CSCL learning environment. The thematic analysis was conducted to analyze the transcribed interviews using a qualitative data analysis software (Nvivo). The analysis followed a six step process: (1) reading interview transcripts multiple times and preliminary in vivo codes; (2) conducting open coding by coding interesting or salient features of the data; (3) collecting codes and searching for themes; (4) reviewing themes and creating a thematic map; (5) finalizing themes and their definitions; and (6) compiling findings. This study found that the students’ use of CSCL resources varied depending on the students’ personal preferences, as well as their perceptions of the given resource’s value and its potential to enhance their learning. For example, the dynamics lecturebook, which had been redesigned to encourage problem solving and note-taking, fostered student collaborative problem solving with their peers. In contrast, the professor’s example video solutions had much more of an influence on students’ independent problem-solving processes. The least frequently used resource was the course’s online discussion forum, which could be used as a means of communication. The findings reveal how computer-supported collaborative learning (CSCL) environments enable engineering students to engage in multiple learning opportunities with diverse and flexible resources to both address and to clarify their personal learning needs. This study strongly recommends engineering instructors adapt a CSCL environment for implementation in their own unique classroom context.
more » « less
5. Summary

We present a spatially varying Robin interface condition for solving fluid‐structure interaction problems involving incompressible fluid flows and nonuniform flexible structures. Recent studies have shown that for uniform structures with constant material and geometric properties, a constant one‐parameter Robin interface condition can improve the stability and accuracy of partitioned numerical solution procedures. In this work, we generalize the parameter to a spatially varying function that depends on the structure's local material and geometric properties, without varying the exact solution of the coupled fluid‐structure system. We present an algorithm to implement the Robin interface condition in an embedded boundary method for coupling a projection‐based incompressible viscous flow solver with a nonlinear finite element structural solver. We demonstrate the numerical effects of the spatially varying Robin interface condition using two example problems: a simplified model problem featuring a nonuniform Euler‐Bernoulli beam interacting with an inviscid flow and a generalized Turek‐Hron problem featuring a nonuniform, highly flexible beam interacting with a viscous laminar flow. Both cases show that a spatially varying Robin interface condition can clearly improve numerical accuracy (by up to two orders of magnitude in one instance) for the same computational cost. Using the second example problem, we also demonstrate and compare two models for determining the local value of the combination function in the Robin interface condition.

more » « less