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
blocktridiagonal forms, respectively, via dierent modications of the Lanczos algorithm. Generally, such realizations
can be interpreted as ladder resistorcapacitorinductor (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 ecient
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 socalled nitedierence Gaussian quadrature rules
(FDGQR), allowing to approximately map the ROM statespace 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 coecients 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 coecients of (63) can be obtained via a
nonsymmetric Lanczos algorithm written in Jsymmetric 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 nitedierence
approximation of the underlying PDE problem [2]. For PDEs in more than one variables (including topologically rich
datamanifolds), a nitedierence interpretation is obtained via a MIMO extensions in block form, e.g., [4, 3].
The main diculty 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 portHamiltonian 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 nonpositivity of conductors for the
nonStieltjes case, we introduce an additional complex sdependent coordinate stretching, vanishing as s → ∞ [1].
This stretching applied in the discrete setting induces a diagonal factorization, removes oscillating coecients, and
leads to an accurate embedding for moderate variations of the coecients of the continuum problems, i.e., it maps
discrete coecients 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 KreinNudelman theory [5], that results in special datadriven 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 Scientic Computing, V. 89, N1, pp. 136,2021
[2] Druskin, Vladimir and Knizhnerman, Leonid, Gaussian spectral rules for the threepoint second dierences:
I. A twopoint positive denite problem in a semiinnite 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 graphLaplacians and cluster analysis, Druskin, Vladimir and Mamonov, Alexander V
and Zaslavsky, Mikhail, Journal of Scientic 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
Machine Learning Framework for Quantum Sampling of HighlyConstrained, Continuous Optimization Problems
In the recent years, there is a growing interest in using quantum computers for solving combinatorial optimization problems. In this work, we developed a generic, machine learningbased framework for mapping continuousspace inverse design problems into surrogate quadratic unconstrained binary optimization (QUBO) problems by employing a binary variational autoencoder and a factorization machine. The factorization machine is trained as a lowdimensional, binary surrogate model for the continuous design space and sampled using various QUBO samplers. Using the DWave Advantage hybrid sampler and simulated annealing, we demonstrate that by repeated resampling and retraining of the factorization machine, our framework finds designs that exhibit figures of merit exceeding those of its training set. We showcase the framework’s performance on two inverse design problems by optimizing (i) thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive metagratings for highly efficient beam steering. This technique can be further scaled to leverage future developments in quantum optimization to solve advanced inverse design problems for science and engineering applications.
more »
« less
 Award ID(s):
 2029553
 NSFPAR ID:
 10288799
 Date Published:
 Journal Name:
 ArXivorg
 ISSN:
 23318422
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Combinatorial optimization problems prevail in engineering and industry. Some are NPhard and thus become difficult to solve on edge devices due to limited power and computing resources. Quadratic Unconstrained Binary Optimization (QUBO) problem is a valuable emerging model that can formulate numerous combinatorial problems, such as MaxCut, traveling salesman problems, and graphic coloring. QUBO model also reconciles with two emerging computation models, quantum computing and neuromorphic computing, which can potentially boost the speed and energy efficiency in solving combinatorial problems. In this work, we design a neuromorphic QUBO solver composed of a swarm of spiking neural networks (SNN) that conduct a populationbased metaheuristic search for solutions. The proposed model can achieve about x20 40 speedup on large QUBO problems in terms of time steps compared to a traditional neural network solver. As a codesign, we evaluate the neuromorphic swarm solver on a 40nm 25mW Resistive RAM (RRAM) ComputeinMemory (CIM) SoC with a 2.25MB RRAMbased accelerator and an embedded Cortex M3 core. The collaborative SNN swarm can fully exploit the specialty of CIM accelerator in matrix and vector multiplications. Compared to previous works, such an algorithmhardware synergized solver exhibits advantageous speed and energy efficiency for edge devices.more » « less

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximumsatisfiability (MAXSAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in realworld scenarios, this problem is typically infeasible even when using stateoftheart algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealingbased solutions. We present the overall approach and compare results from the DWave quantum annealer against the bestknown classical algorithms such as the Hamzede FreitasSelby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.more » « less

Quadratic Unconstrained Binary Optimization (QUBO) problem becomes an attractive and valuable optimization problem formulation in that it can easily transform into a variety of other combinatorial optimization problems such as Graph/number Partition, MaxCut, SAT, Vertex Coloring, TSP, etc. Some of these problems are NPhard and widely applied in industry and scientific research. Meanwhile, QUBO has been discovered to be compatible with two emerging computing paradigms, neuromorphic computing, and quantum computing, with tremendous potential to speed up future optimization solvers. In this paper, we propose a novel neuromorphic computing paradigm that employs multiple collaborative spiking neural networks to solve QUBO problems. Each SNN conducts a local stochastic gradient descent search and shares the global best solutions periodically to perform a metaheuristic search for optima. We simulate our model and compare it to a single SNN solver and a multSNN solver without collaboration. Through tests on benchmark problems, the proposed method is demonstrated to be more efficient and effective in searching for QUBO optima. Specifically, it exhibits x10 and x1520 speedup respectively on the multiSNN solver without collaboration and the singleSNN solver.more » « less

Many kinds of algorithms have been developed for solving the constraint satisfaction problem (WCSP), a combinatorial optimization problem that frequently appears in AI. Unfortunately, its NPhardness prohibits the existence of an algorithm for solving it that is universally efficient on classical computers. Therefore, a peek into quantum computers may be imperative for solving the WCSP efficiently. In this paper, we focus on a specific type of quantum computer, called the quantum annealer, which approximately solves quadratic unconstrained binary optimization (QUBO) problems. We propose the first three hybrid quantumclassical algorithms (HQCAs) for the WCSP: one specifically for the binary Boolean WCSP and the other two for the general WCSP. We experimentally show that the HQCA based on simple polynomial reformulation works well on the binary Boolean WCSP, but the HQCA based on the constraint composite graph works best on the general WCSP.more » « less