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 dierent 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-dierence 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 stiness, 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-dierence
approximation of the underlying PDE problem [2]. For PDEs in more than one variables (including topologically rich
data-manifolds), a nite-dierence 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. 136,2021
[2] Druskin, Vladimir and Knizhnerman, Leonid, Gaussian spectral rules for the three-point second dierences:
I. A two-point positive de nite problem in a semi-in nite domain, SIAM Journal on Numerical Analysis, V. 37,
N 2, pp.403422, 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 130, 2022
[4] Druskin, Vladimir and Moskow, Shari and Zaslavsky, Mikhail LippmannSchwingerLanczos 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 49184934
Go back to Plenary Speakers Go back to Speakers Go back
more »
« less
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Systems
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling).
In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations.
We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration.
To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.
more »
« less
- Award ID(s):
- 2007009
- NSF-PAR ID:
- 10420889
- Editor(s):
- Tauman Kalai, Yael
- Date Published:
- Journal Name:
- Leibniz international proceedings in informatics
- Volume:
- 251
- ISSN:
- 1868-8969
- Page Range / eLocation ID:
- 69:1-69:22
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Bojanczyk, Mikolaj ; Chekuri, Chandra (Ed.)Given a point set P in the plane, we seek a subset Q ⊆ P, whose convex hull gives a smaller and thus simpler representation of the convex hull of P. Specifically, let cost(Q,P) denote the Hausdorff distance between the convex hulls CH(Q) and CH(P). Then given a value ε > 0 we seek the smallest subset Q ⊆ P such that cost(Q,P) ≤ ε. We also consider the dual version, where given an integer k, we seek the subset Q ⊆ P which minimizes cost(Q,P), such that |Q| ≤ k. For these problems, when P is in convex position, we respectively give an O(n log²n) time algorithm and an O(n log³n) time algorithm, where the latter running time holds with high probability. When there is no restriction on P, we show the problem can be reduced to APSP in an unweighted directed graph, yielding an O(n^2.5302) time algorithm when minimizing k and an O(min{n^2.5302, kn^2.376}) time algorithm when minimizing ε, using prior results for APSP. Finally, we show our near linear algorithms for convex position give 2-approximations for the general case.more » « less
-
null (Ed.)We consider the classical Minimum Balanced Cut problem: given a graph $G$, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first {\em deterministic, almost-linear time} approximation algorithm for this problem. Specifically, our algorithm, given an $n$-vertex $m$-edge graph $G$ and any parameter $1\leq r\leq O(\log n)$, computes a $(\log m)^{r^2}$-approximation for Minimum Balanced Cut on $G$, in time $O\left ( m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$. In particular, we obtain a $(\log m)^{1/\epsilon}$-approximation in time $m^{1+O(1/\sqrt{\epsilon})}$ for any constant $\epsilon$, and a $(\log m)^{f(m)}$-approximation in time $m^{1+o(1)}$, for any slowly growing function $m$. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of $G$ that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an $n$-vertex graph is $n^{o(1)}$, thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in $n$ factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.more » « less
-
We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is O(ε−1). In this paper, we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of O ε−2/(2+β) log2(ε−1), where β ∈ (0, 1] is a local error bound parameter. As an example application of the general algorithm, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with β = 1/2, therefore enjoying a convergence time of O ε−4/5 log2(ε−1). This result improves upon the O(ε−1) convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.more » « less
-
null (Ed.)The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)-approximation in Õ(n) time or 3.5-approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)-Convolution conjecture, showing that approxima- tions are inevitable in the near-linear time regime. To complement the lower bound, we provide a 3.3-approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Building on our construction we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. At the core of our constructions is a diamond-like gadget that also settles the complexity of Diameter in distributed planar networks. We prove an Ω(n/ log n) lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGET model, even when the underlying graph is planar and all nodes are D = 4 hops away from each other. This is the first poly(n) lower bound in the planar-distributed setting, and it complements the recent poly(D, log n) upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for (1 + ε) approximate weighted diameter.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
