Search

We study a system of ordinary differential equations in R5 that is used as a model both in population dynamics and in game theory and is known to exhibit a heteroclinic network consisting in the union of four types of elementary heteroclinic cycles. We show the asymptotic stability of the network for parameter values in a range compatible with both population and game dynamics. We obtain estimates of the relative attractiveness of each one of the cycles by computing their stability indices. For the parameter values ensuring the asymptotic stability of the network we relate the attractiveness properties of each cycle to the others. In particular, for three of the cycles we show that if one of them has a weak form of attractiveness, then the other two are completely unstable. We also show the existence of an open region in parameter space where all four cycles are completely unstable and the network is asymptotically stable, giving rise to intricate dynamics that has been observed numerically by other authors. [ABSTRACT FROM AUTHOR]

Image denoising-removal of additive white Gaussian noise from an image-is one of the oldest and most studied problems in image processing. Extensive work over several decades has led to thousands of papers on this subject, and to many well-performing algorithms for this task. Indeed, 10 years ago, these achievements led some researchers to suspect that "Denoising is Dead, in the sense that all that can be achieved in this domain has already been obtained. However, this turned out to be far from the truth, with the penetration of deep learning (DL) into the realm of image processing. The era of DL brought a revolution to image denoising, both by taking the lead in today's ability for noise suppression in images, and by broadening the scope of denoising problems being treated. Our paper starts by describing this evolution, highlighting in particular the tension and synergy that exist between classical approaches and modern artificial intelligence (AI) alternatives in design of image denoisers. The recent transitions in the field of image denoising go far beyond the ability to design better denoisers. In the second part of this paper we focus on recently discovered abilities and prospects of image denoisers. We expose the possibility of using image denoisers for service of other problems, such as regularizing general inverse problems and serving as the prime engine in diffusion-based image synthesis. We also unveil the (strange?) idea that denoising and other inverse problems might not have a unique solution, as common algorithms would have us believe. Instead, we describe constructive ways to produce randomized and diverse high perceptual quality results for inverse problems, all fueled by the progress that DL brought to image denoising. This is a survey paper, and its prime goal is to provide a broad view of the history of the field of image denoising and closely related topics in image processing. Our aim is to give a better context to recent discoveries, and to the influence of the AI revolution in our domain. [ABSTRACT FROM AUTHOR]

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\'a, SIAM J. Comput., 10 (1981), pp. 270--283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290--306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815--825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632--645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) 967 1120 + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP'14, Springer, Berlin, 2014, pp. 800--811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we "open the box" and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area. [ABSTRACT FROM AUTHOR]

The article focuses on research reproducibility in scientific computing journals, Journal on Scientific Computing (SISC), Journal of Scientific Computing (JSC), and Journal of Computational Physics (JCP), by requiring authors to publicly share their data and credibility in scientific research.

In this paper, we introduce the ensemble Kaiman--Stein gradient descent (EnKSGD) class of algorithms. The EnKSGD class of algorithms builds on the ensemble Kalman filter (EnKF) line of work, applying techniques from sequential data assimilation to unconstrained optimization and parameter estimation problems. An essential idea is to exploit the EnKF as a black box (i.e., derivative-free, zeroth order) optimization tool if iterated to convergence. In this paper, we return to the foundations of the EnKF as a sequential data assimilation technique, including its continuous-time and mean-field limits, with the goal of developing faster optimization algorithms suited to noisy black box optimization and inverse problems. The resulting EnKSGD class of algorithms can be designed to both maintain the desirable property of affine-invariance and employ the well-known backtracking line search. Furthermore, EnKSGD algorithms are designed to not necessitate the subspace restriction property and to avoid the variance collapse property of previous iterated EnKF approaches to optimization, as both these properties can be undesirable in an optimization context. EnKSGD also generalizes beyond the L² loss and is thus applicable to a wider class of problems than the standard EnKF. Numerical experiments with empirical risk minimization type problems, including both linear and nonlinear least squares problems, as well as maximum likelihood estimation, demonstrate the faster empirical convergence of EnKSGD relative to alternative EnKF approaches to optimization. [ABSTRACT FROM AUTHOR]

In this paper, we consider the adaptive stabilization problem for a basic class of linearquadratic noncooperative stochastic differential games when the systems matrices are unknown to the regulator and the players. This is a typical problem of game-based control systems (GBCS) introduced and studied recently, which have a hierarchical decision-making structure: there is a controller at the upper level acting as a global regulator which makes its decision first, and the players at the lower level are assumed to play a typical zero-sum differential games. The main purpose of the paper is to study how the adaptive regulator can be designed to make the GBCS globally stable and at the same time to ensure a Nash equilibrium reached by the players, where the adaptive strategies of the players are assumed to be constructed based on the standard least squares estimators. The design of the global regulator is an integration of the weighted least squares parameter estimator, random regularization and diminishing excitation methods. Under the assumption that the system matrix pair (A, B) is controllable and there exists a stabilizing solution for the corresponding algebraic Riccati equation, it is shown that the closed-loop adaptive GBCS will be globally stable, and at the same time reach a Nash equilibrium by the players. [ABSTRACT FROM AUTHOR]

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections. [ABSTRACT FROM AUTHOR]

In this paper, we study optimal stochastic control problems for stochastic systems driven by non-Markov subdiffusion BLt, which have mixed features of deterministic and stochastic controls. Here Bt is the standard Brownian motion on R, and Lt := inf { r > 0 : Sr > t}, t ≥ 0, is the inverse of a subordinator St with drift κ > 0 that is independent of Bt. We obtain stochastic maximum principles (SMPs) for these systems using both convex and spiking variational methods, depending on whether or not the domain is convex. To derive SMPs, we first establish a martingale representation theorem for subdiffusions BLt , and then use it to derive the existence and uniqueness result for the solutions of backward stochastic differential equations (BSDEs) driven by subdiffusions, which may be of independent interest. We also derive sufficient SMPs. Application to a linear quadratic system is given to illustrate the main results of this paper. [ABSTRACT FROM AUTHOR]

This paper aims to present a novel isotropic bidirectional model for studying weakly dispersive and weakly nonlinear atmospheric internal waves in a three-dimensional system consisting of two superimposed, incompressible, and inviscid fluids. The newly developed equation is the Benjamin-Benney-Luke (BBL) equation, a generalization of the famous two-dimensional Benjamin-Ono (2DBO) equation and the Benney-Luke equation, derived using the nonlocal Ablowitz-Fokas-Musslimani formulation of water waves. The evolution results of the BBL and 2DBO equations, performed by implementing the classic fourth-order Runge-Kutta method, the pseudospectral scheme with the integrating factor method, and the windowing scheme, show that the anisotropic 2DBO equation agrees well with the isotropic BBL model for problems being investigated, namely the focus is the central part of the soliton evolution/interaction zone. By applying the Whitham modulation theory, modulation equations for the 2DBO equation are obtained in this paper for analyzing the soliton dynamics in five different initial-value problems (truncated line soliton, line soliton, bent-stem soliton, bent soliton, and reverse bent soliton). In addition, corresponding numerical results are obtained and shown to agree well with the theoretical predictions. Both theoretical and numerical results reveal the formation conditions of the Mach expansion, as well as the specific relationship between the amplitude of the Mach stem and the initial data. [ABSTRACT FROM AUTHOR]

In this paper, we study the Lipschitz continuous dependence of conservative H\"older continuous weak solutions to a variational wave system derived from a model for nematic liquid crystals. Since the solution of this system generally forms a finite time cusp singularity, the solution flow is not Lipschitz continuous under the Sobolev metric used in the existence and uniqueness theory. We establish a Finsler type optimal transport metric, and show the Lipschitz continuous dependence of the solution on the initial data under this metric. This kind of Finsler type optimal transport metrics was first established in [A. Bressan and G. Chen, Arch. Ration. Mech. Anal., 226 (2017), pp. 1303-1343] for the scalar variational wave equation. This equation can be used to describe the unit direction n of mean orientation of nematic liquid crystals, when n is restricted on a circle. The model considered in this paper describes the propagation of n without this restriction, i.e. n, takes any value on the unit sphere. So we need to consider a wave system instead of a scalar equation. [ABSTRACT FROM AUTHOR]

This paper deals with the stability analysis for steady-states perturbed by the full cross-diffusion limit of the SKT model with Dirichlet boundary conditions. Our previous result showed that positive steady-states consist of the branch of small coexistence type bifurcating from the trivial solution and the branches of segregation type bifurcating from points on the branch of small coexistence type. This paper shows the Morse index of steady-states on the branches and constructs the local unstable manifold around each steady-state of which the dimension is equal to the Morse index. [ABSTRACT FROM AUTHOR]

This paper focuses on systems of nonlinear second-order stochastic differential equations with multiscales. The motivation for our study stems from mathematical physics and statistical mechanics, for example, Langevin dynamics and stochastic acceleration in a random environment. Our aim is to carry out asymptotic analysis to establish large deviations principles. Our focus is on obtaining the desired results for systems under weaker conditions. When the fast-varying process is a diffusion, neither Lipschitz continuity nor linear growth needs to be assumed. Our approach is based on combinations of the intuition from Smoluchowski--Kramers approximation and the methods initiated in [A. A. Puhalskii, Ann. Probab., 44 (2016), pp. 3111--3186] relying on the concepts of relatively large deviations compactness and the identification of rate functions. When the fast-varying process is under a general setup with no specified structure, the paper establishes the large deviations principle of the underlying system under the assumption on the local large deviations principles of the corresponding first-order system. [ABSTRACT FROM AUTHOR]

In this paper, we study the following Minimum Cost Multicovering (MCMC) problem: Given a set of n client points C and a set of m server points S in a fixed dimensional Rd space, determine a set of disks centered at these server points so that each client point c is covered by at least k(c) disks and the total cost of these disks is minimized, where k(·) is a function that maps every client point to some nonnegative integer no more than m and the cost of each disk is measured by the \alpha th power of its radius for some constant α >0. MCMC is a fundamental optimization problem with applications in many areas such as wireless/sensor networking. Despite extensive research on this problem for about two decades, only constant approximations were known for general k. It has been a long standing open problem to determine whether a PTAS is possible. In this paper, we give an affirmative answer to this question by presenting the first PTAS for it. Our approach is based on a number of novel techniques, such as balanced recursive realization and bubble charging, and new counterintuitive insights to the problem. Particularly, we approximate each disk with a set of sub-boxes and optimize them at the subdisk level. This allows us to first compute an approximate disk cover through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. [ABSTRACT FROM AUTHOR]

This paper surveys an important class of methods that combine iterative projection methods and variational regularization methods for large-scale inverse problems. Iterative methods such as Krylov subspace methods are invaluable in the numerical linear algebra community and have proved important in solving inverse problems due to their inherent regularizing properties and their ability to handle large-scale problems. Variational regularization describes a broad and important class of methods that are used to obtain reliable solutions to inverse problems, whereby one solves a modified problem that incorporates prior knowledge. Hybrid projection methods combine iterative projection methods with variational regularization techniques in a synergistic way, providing researchers with a powerful computational framework for solving very large inverse problems. Although the idea of a hybrid Krylov method for linear inverse problems goes back to the 1980s, several recent advances on new regularization frameworks and methodologies have made this field ripe for extensions, further analyses, and new applications. In this paper, we provide a practical and accessible introduction to hybrid projection methods in the context of solving large (linear) inverse problems. [ABSTRACT FROM AUTHOR]

The mystery of soaring birds, such as albatrosses and eagles, has intrigued biologists, physicists, aeronautical/control engineers, and applied mathematicians for centuries. These fascinating avian organisms are able to fly for long durations while expending little to no energy, utilizing wind to gain lift. This flight technique/maneuver is called dynamic soaring (DS). For biologists and physicists, the DS phenomenon is nothing but a wonder of the very elegant ability of these birds to interact with nature and use its physical ether in an optimal way for better survival and energy efficiency. For the engineering community, the DS phenomenon is a source of inspiration and an unequivocal opportunity for biomimicking. Mathematical characterization of the DS phenomenon in the literature has been limited to optimal control configurations that utilized developments in numerical optimization algorithms along with control methods to identify the optimal DS trajectory taken (or to be taken) by the bird/mimicking system. Unfortunately, all of these methods are highly complex and non-real-time. Hence, the mathematical characterization of the DS problem, we believe, appears to be at odds with the phenomenon/birds-behavior. In this paper, we provide a novel twolayered mathematical approach to characterize, model, mimic, and control DS in a simple real-time implementation, which we believe more effectively decodes the biological behavior of soaring birds. First, we present a differential geometric control formulation and analysis of the DS problem, which allow us to introduce a control system that is simple yet controllable. Second, we establish a link between the DS philosophy and a class of dynamical control systems known as extremum seeking systems. This linkage provides the control input that makes DS a real-time reality. We believe our framework accurately describes the biological behavior of soaring birds and opens the door for geometric control theory and extremum seeking systems to be utilized in biological systems and natural phenomena. Simulation results are provided along with comparisons to powerful optimal control solvers, illustrating the advantages of the introduced method. [ABSTRACT FROM AUTHOR]

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt, we denote a path on t vertices. In this paper, we give polynomial-time algorithms for the following problems: the maximum weight independent set problem in long-hole--free graphs and the feedback vertex set problem in P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let C be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; C contains all long-hole--free graphs and all P5-free graphs. We show that, given an n-vertex graph G\in C with vertex weights and an integer k, one can, in time, n\scrO (k) find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput., 31 (2001), pp. 212--232] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54--87], this framework allows us to solve a wide variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the maximum weight independent set problem within this framework (e.g., for P5-free [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp. 570--581] or P6-free graphs [Grzesik, Klimo\v sov\'a, Pilipczuk, and Pilipczuk, ACM Trans. Algorithms, 18 (2022), pp. 4:1--4:57]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here, we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each PMC: a superset of the maximal clique that intersects the sought solution only in the vertices of the PMC. This strengthening of the framework not only allows us to obtain our main result but also leads to significant simplifications of the reasoning in previous papers. [ABSTRACT FROM AUTHOR]

In this paper, we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer to as the BB-preconditioner. A series of numerical tests show that the BB-preconditioner is the most efficient among those presented, despite a performance deterioration in the last steps of the interior point method. It is in fact the only one having a CPU time that scales only slightly worse than linearly with respect to the number of unknowns used to discretize the problem. [ABSTRACT FROM AUTHOR]

For a nonlinear dynamical system that depends on parameters, this paper introduces a novel tensorial reduced-order model (TROM). The reduced model is projection-based, and for systems with no parameters involved, it resembles proper orthogonal decomposition (POD) combined with the discrete empirical interpolation method (DEIM). For parametric systems, TROM employs low-rank tensor approximations in place of truncated SVD, a key dimension-reduction technique in POD with DEIM. Three popular low-rank tensor compression formats are considered for this purpose: canonical polyadic, Tucker, and tensor train. The use of multilinear algebra tools allows the incorporation of information about the parameter dependence of the system into the reduced model and leads to a POD-DEIM type ROM that (i) is parameter-specific (localized) and predicts the system dynamics for out-of-training set (unseen) parameter values, (ii) mitigates the adverse effects of high parameter space dimension, (iii) has online computational costs that depend only on tensor compression ranks but not on the full-order model size, and (iv) achieves lower reduced space dimensions compared to the conventional POD-DEIM ROM. This paper explains the method, analyzes its prediction power, and assesses its performance for two specific parameter-dependent nonlinear dynamical systems. [ABSTRACT FROM AUTHOR]

In this paper, we first derive a time-dependent Maxwell's equation model for simulating wave propagation in anisotropic dispersive media and hyperbolic metamaterials. The modeling equations are obtained by using the Drude--Lorentz model to approximate both the permittivity and permeability. Then we develop a time-domain finite element method and prove its discrete stability and optimal error estimate. This mathematical model and the proposed numerical method can be used to design effective hyperbolic superlenses by the dielectric-metal multilayer metamaterials in different frequency ranges. Extensive two-dimensional (2D) and 3D numerical results are presented to demonstrate the good performance of many 2D and 3D hyperbolic superlenses in different frequency ranges. This is the first finite element paper on solving the hyperbolic metamaterials in a time domain. [ABSTRACT FROM AUTHOR]

This paper is concerned with the multi-frequency factorization method for imaging the support of a wave-number-dependent source function. It is supposed that the source function is given by the inverse Fourier transform of some time-dependent source with a priori given radiating period. Using the multi-frequency far-field data at a fixed observation direction, we provide a computational criterion for characterizing the smallest strip containing the support and perpendicular to the observation direction. The far-field data from sparse observation directions can be used to recover a Θ-convex polygon of the support. The inversion algorithm is proven valid even with multi-frequency near-field data in three dimensions. The connections to time-dependent inverse source problems are discussed in the near-field case. Numerical tests in both two and three dimensions are implemented to show effectiveness and feasibility of the approach. This paper provides numerical analysis for a frequency-domain approach to recover the support of an admissible class of time-dependent sources. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with the tracking performance and antidisturbance ability of the widely used proportional-integral-derivative (PID) controllers in practice. Towards this end, we consider a basic class of second-order nonlinear stochastic control systems subject to model uncertainties and external disturbances, and focus on the ability of the classical PID controller to track time-varying reference signals. First, under some suitable conditions on the system nonlinear functions, reference signals, and external disturbances, we show that such control systems can be stabilized in the mean square sense, provided that the three PID gains are selected from a stability region constructed in the paper. Besides, it is shown that the steady-state tracking error has an upper bound proportional to the sum of the varying rates of reference signals, the varying rates of external disturbances, and the intensity of random noises. Meanwhile, its proportional coefficient depends on the selection of PID gains, which can be made arbitrarily small by choosing suitably large PID gains. Finally, by introducing a desired transient process which is shaped from the reference signal, a new PID tuning rule is presented, which can guarantee both the expected steady state and transient tracking performance. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a general linear time-invariant multiagent system with heterogeneous actuator saturation to answer the main question: how to achieve global consensus under the premise of asymptotically null controllable with bounded controls of each agent so as to make breakthroughs from the perspectives of global consensus, heterogeneous actuator saturation, communication noises, and distributed characteristic preservation. We introduce a distributed control algorithm that incorporates a redesigned saturation function featuring a decentralized dynamic saturation level to achieve these objectives. Each component of the dynamic saturation level self-updates according to an adaptive strategy. The proposed method effectively eliminates heterogeneous actuator saturation by carefully selecting both the constant and time-varying saturation parameters in the adaptive strategy of the dynamic saturation level. Our approach achieves both state feedback--based and output feedback--based global consensus, with the latter utilizing a special coordinate decomposition. Numerical simulations demonstrate the efficacy of our method. [ABSTRACT FROM AUTHOR]

We consider dynamic games defined over an infinite horizon, characterized by linear, discrete-time dynamics and quadratic cost functionals. Considering such linear-quadratic dynamic games, we focus on their solutions in terms of Nash equilibrium strategies. Both feedback (F-NE) and open-loop (OL-NE) Nash equilibrium solutions are considered. The contributions of the paper are threefold. First, our detailed study reveals some interesting structural insights in relation to F-NE solutions. Second, as a stepping stone toward our consideration of OL-NE strategies, we consider a specific infinite-horizon discrete-time (single-player) optimal control problem, wherein the dynamics are influenced by a known exogenous input and draw connections between its solution obtained via dynamic programming and Pontryagin's minimum principle. Finally, we exploit the latter result to provide a characterization of OL-NE strategies of the class of infinite-horizon dynamic games. The results and key observations made throughout the paper are illustrated via a numerical example. [ABSTRACT FROM AUTHOR]

In this paper, we study the temperature distribution of a body when the heat is transmitted only by radiation. The heat transmitted by convection and conduction is ignored. We consider the stationary radiative transfer equation in local thermodynamic equilibrium. We prove that the stationary radiative transfer equation coupled with the nonlocal temperature equation is well-posed in general geometries when emission-absorption or scattering of interacting radiation is considered. The emission-absorption and the scattering coefficients are assumed to be general, and they can depend on the frequency of radiation. We also establish an entropy production formula of the system which is used to prove the uniqueness of solutions for an incoming radiation with constant temperature. [ABSTRACT FROM AUTHOR]

In this paper, we establish new results for the uniform far-field asymptotics of the two-layered Green function (together with its derivatives) in two dimensions in the frequency domain. To the best of our knowledge, our results are the sharpest yet obtained. The steepest descent method plays an important role in the proofs of our results. Further, as an application of our new results, we derive the uniform far-field asymptotics of the scattered field to the acoustic scattering problem by buried obstacles in a two-layered medium with a locally rough interface. The results obtained in this paper provide a theoretical foundation for our recent work, where direct imaging methods have been developed to image the locally rough interface from phaseless total-field data or phased far-field data at a fixed frequency. It is believed that the results obtained in this paper will also be useful on its own right. [ABSTRACT FROM AUTHOR]

This document is a special section of the SIAM Journal on Computing, focusing on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018). It includes ten fully refereed papers that were presented at the symposium in Paris in October 2018. The papers cover a wide range of topics, including complexity theory, graph algorithms, approximation algorithms, cryptography, quantum computing, pseudorandom generators, matrix multiplication, and graph sparsification. The papers underwent an extensive refereeing process, and the authors and anonymous referees are thanked for their efforts. The special section was prepared with the help of the guest editors and the SIAM Publications Manager. [Extracted from the article]

We consider a random permutation Τn uniformly distributed on the set of all per- mutations of degree n whose cycle lengths lie in a fixed set A (the so-called A-permutations). Let ζn be the total number of cycles, and let ηn(1) ≥ ηn(2) ≥ • • • ≥ ηn(ζn) be the ordered sample of cycle lengths of the permutation Τn. We consider a class of sets A with positive density in the set of natural numbers. We study the asymptotic behavior of ηn(m) with numbers m in the left-hand and middle parts of this series for a class of sets of positive asymptotic density. A limit theorem for the rightmost terms of this series was proved by the author of this note earlier. The study of limit properties of the sequence ηn(m) dates back to the paper by Shepp and Lloyd [Trans. Amer. Math. Soc., 121 (1966), pp. 340--357] who considered the case A = N. [ABSTRACT FROM AUTHOR]

Though there are hundreds of papers on rational spectral factorization, most of them are concerned with full-rank spectral densities. In this paper we propose a novel approach for spectral factorization of a rank-deficient spectral density, leading to a minimum-phase full-rank spectral factor, in both the discrete-time and continuous-time cases. Compared with several approaches to low-rank spectral factorization, our approach exploits a deterministic relation inside the factor, leading to high computational efficiency. In addition, we show that this method is easily used in identification of low-rank processes and in Wiener filtering. [ABSTRACT FROM AUTHOR]

The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTrace and XNysTrace, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard--Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs. [ABSTRACT FROM AUTHOR]

We establish a large deviation principle (LDP) for a class of stochastic porous media equations driven by Lévy-type noise on a σ-finite measure space (E,B(E),μ), with the Laplacian replaced by a negative definite self-adjoint operator. One of the main contributions of this paper is that we do not assume the compactness of embeddings in the corresponding Gelfand triple, and to compensate for this generalization, a new procedure is provided. This is the first paper to deal with LDPs for stochastic evolution equations with Lévy noise without compactness conditions. The coefficient Ψ is assumed to satisfy nondecreasing Lipschitz nonlinearity, so an important physical problem covered by this case is the Stefan problem. Numerous examples of negative definite self-adjoint operators are applicable to our results, for example, for open E⊂Rd, L= Laplacian or fractional Laplacians, i.e., L=-(-Δ)α, α∈(0,1], generalized Schrödinger operators, i.e., L=Δ+2∇ρ/ρ⋅∇, Laplacians on fractals is also included. [ABSTRACT FROM AUTHOR]

The SIAM Journal on Applied Mathematics has published a special section on the life sciences, highlighting the use of mathematical models and analysis in understanding biological systems. The section showcases a range of topics, including population dynamics, genetics, neuroscience, epidemics, and various physiological systems. The papers in the section focus on providing biological insights or suggesting novel experiments, and they incorporate practical issues, data-driven modeling, and uncertainty quantification. The special section reflects the growing interest and activity in the fields of mathematical and computational biology, which have been driven by real-world applications in health, medicine, and bioengineering. [Extracted from the article]

In this paper, we give an in-depth error analysis for surrogate models generated by a variant of the Sparse Identification of Nonlinear Dynamics (SINDy) method. We start with an overview of a variety of nonlinear system identification techniques, namely SINDy, weak-SINDy, and the occupation kernel method. Under the assumption that the dynamics are a finite linear combination of a set of basis functions, these methods establish a linear system to recover coefficients. We illuminate the structural similarities between these techniques and establish a projection property for the weak-SINDy technique. Following the overview, we analyze the error of surrogate models generated by a simplified version of weak-SINDy. In particular, under the assumption of boundedness of a composition operator given by the solution, we show that (i) the surrogate dynamics converges towards the true dynamics and (ii) the solution of the surrogate model is reasonably close to the true solution. Finally, as an application, we discuss the use of a combination of weak-SINDy surrogate modeling and proper orthogonal decomposition (POD) to build a surrogate model for partial differential equations (PDEs). [ABSTRACT FROM AUTHOR]

In this paper, we study a class of unconstrained and constrained bilevel optimization problems in which the lower level is a possibly nonsmooth convex optimization problem, while the upper level is a possibly nonconvex optimization problem. We introduce a notion of varepsilon -KKT solution for them and show that an varepsilon -KKT solution leads to an...-hypergradient--based stationary point under suitable assumptions. We also propose first-order penalty methods for finding an varepsilon -KKT solution of them, whose subproblems turn out to be a structured minimax problem and can be suitably solved by a first-order method recently developed by the authors. Under suitable assumptions, an operation complexity of... 1), measured by their fundamental operations, is established for the proposed penalty methods for finding an varepsilon-KKT solution of the unconstrained and constrained bilevel optimization problems, respectively. Preliminary numerical results are presented to illustrate the performance of our proposed methods. To the best of our knowledge, this paper is the first work to demonstrate that bilevel optimization can be approximately solved as minimax optimization, and moreover, it provides the first implementable method with complexity guarantees for such sophisticated bilevel optimization. [ABSTRACT FROM AUTHOR]

In the past several years, augmented Lagrangian methods have been successfully applied to several classes of nonconvex optimization problems, inspiring new developments in both theory and practice. In this paper we bring most of these recent developments from nonlinear programming to the context of optimization on Riemannian manifolds, including equality and inequality constraints. Many research have been conducted on optimization problems on manifolds, however only recently the treatment of the constrained case has been considered. In this paper we propose to bridge this gap with respect to the most recent developments in nonlinear programming. In particular, we formulate several well-known constraint qualifications from the Euclidean context which are sufficient for guaranteeing global convergence of augmented Lagrangian methods, without requiring boundedness of the set of Lagrange multipliers. Convergence of the dual sequence can also be assured under a weak constraint qualification. The theory presented is based on so-called sequential optimality conditions, which is a powerful tool used in this context. The paper can also be read with the Euclidean context in mind, serving as a review of the most relevant constraint qualifications and global convergence theory of state-of-the-art augmented Lagrangian methods for nonlinear programming. [ABSTRACT FROM AUTHOR]

We consider optimal control problems for partial differential equations where the controls take binary values but vary over the time horizon; they can thus be seen as dynamic switches. The switching patterns may be sub ject to combinatorial constraints such as, e.g., an upper bound on the total number of switchings or a lower bound on the time between two switchings. In a companion paper [C. Buchheim, A. Gruütering, and C. Meyer, SIAM J. Optim., arXiv:2203.07121, 2024], we describe the Lp -closure of the convex hull of feasible switching patterns as the intersection of convex sets derived from finite-dimensional pro jections. In this paper, the resulting outer description is used for the construction of an outer approximation algorithm in function space, whose iterates are proven to converge strongly in L² to the global minimizer of the convexified optimal control problem. The linear-quadratic subproblems arising in each iteration of the outer approximation algorithm are solved by means of a semismooth Newton method. A numerical example in two spatial dimensions illustrates the efficiency of the overall algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a new accelerated proximal Markov chain Monte Carlo methodology to perform Bayesian inference in imaging inverse problems with an underlying convex geometry. The proposed strategy takes the form of a stochastic relaxed proximal-point iteration that admits two complementary interpretations. For models that are smooth or regularized by Moreau-Yosida smoothing, the algorithm is equivalent to an implicit midpoint discretization of an overdamped Langevin diffusion targeting the posterior distribution of interest. This discretization is asymptotically unbiased for Gaussian targets and shown to converge in an accelerated manner for any target that is κ-strongly log-concave (i.e., requiring in the order of √κ iterations to converge, similar to accelerated optimization schemes), comparing favorably to Pereyra, Vargas Mieles, and Zygalakis [SIAM J. Imaging Sci., 13 (2020), pp. 905-935], which is only provably accelerated for Gaussian targets and has bias. For models that are not smooth, the algorithm is equivalent to a Leimkuhler-Matthews discretization of a Langevin diffusion targeting a Moreau-Yosida approximation of the posterior distribution of interest and hence achieves a significantly lower bias than conventional unadjusted Langevin strategies based on the Euler-Maruyama discretization. For targets that are κ-strongly log-concave, the provided nonasymptotic convergence analysis also identifies the optimal time step, which maximizes the convergence speed. The proposed methodology is demonstrated through a range of experiments related to image deconvolution with Gaussian and Poisson noise with assumption-driven and data-driven convex priors. Source codes for the numerical experiments of this paper are available from https://github.com/MI2G/accelerated-langevin-imla. [ABSTRACT FROM AUTHOR]

Neural networks allow solving many ill-posed inverse problems with unprecedented performance. Physics informed approaches already progressively replace carefully hand-crafted reconstruction algorithms in real applications. However, these networks suffer from a major defect: when trained on a given forward operator, they do not generalize well to a different one. The aim of this paper is twofold. First, we show through various applications that training the network with a family of forward operators allows solving the adaptivity problem without compromising the reconstruction quality significantly. Second, we illustrate that this training procedure allows tackling challenging blind inverse problems. Our experiments include partial Fourier sampling problems arising in magnetic resonance imaging with sensitivity estimation and off-resonance effects, computerized tomography with a tilted geometry, and image deblurring with Fresnel diffraction kernels. [ABSTRACT FROM AUTHOR]

DEM simulations by Chialvo et al. observed three distinct flow regimes for homogeneous simple shear of soft, frictional, noncohesive spheres in different domains of shear rate and density. This paper shows that all three regimes can be accommodated in a continuum description, using the CIDR formalism. [ABSTRACT FROM AUTHOR]

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate Ω(ε(log(1/∈)+1) that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist (1-ε,l,O(l/ε)) -list-recoverable RS codes with rate Ω(εl√(log(1/ε)+1)) . Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable. [ABSTRACT FROM AUTHOR]

Low Reynolds number fluid flows are governed by the Stokes equations. In two dimensions, Stokes flows can be described by two analytic functions, known as Goursat functions. Brubeck and Trefethen [SIAM J. Sci. Comput., 44 (2022), pp. A1205-A1226] recently introduced a lightning Stokes solver that uses rational functions to approximate the Goursat functions in polyg- onal domains. In this paper, we present the LARS algorithm (lightning-AAA rational Stokes) for computing two-dimensional (2D) Stokes flows in domains with smooth boundaries and multiply con- nected domains using lightning and AAA rational approximation [Y. Nakatsukasa, O. Sète, and L. N. Trefethen, SIAM J. Sci. Comput., 40 (2018), pp. A1494-A1522]. After validating our solver against known analytical solutions, we solve a variety of 2D Stokes flow problems with physical and engineering applications. Using these examples, we show rational approximation can now be used to compute 2D Stokes flows in general domains. The computations take less than a second and give solutions with at least 6-digit accuracy. [ABSTRACT FROM AUTHOR]

The weighted essentially nonoscillatory (WENO) schemes are popular high-order numerical methods for hyperbolic conservation laws. When dealing with hyperbolic systems, WENO schemes are usually used in cooperation with the local characteristic decomposition, as the componentwise WENO reconstruction/interpolation procedure often produces oscillatory approximations near shocks. In this paper, we investigate local characteristic decomposition-free WENO schemes for a special class of hyperbolic systems endowed with a coordinate system of Riemann invariants. We apply the WENO procedure to the coordinate system of Riemann invariants instead of the local characteristic fields to save the expensive computational cost on local characteristic decomposition but meanwhile maintain the essentially nonoscillatory performance. Due to the nonlinear algebraic relation between the Riemann invariants and conserved variables, it is difficult to obtain the cell averages of Riemann invariants directly from those of conserved variables and vice versa; thus, we do not use the finite volume WENO schemes in this work. The same difficulty is also faced in the traditional Shu-Osher lemma [C.-W. Shu and S. Osher, J. Comput. Phys., 83 (1989), pp. 32-78]-based finite difference schemes, as the computation of fluxes is based on reconstruction as well. Therefore, we adopt the alternative formulation of the finite difference WENO scheme [Y. Jiang, C.-W. Shu, and M. Zhang, SIAM J. Sci. Comput., 35 (2013), pp. A1137-A1160, C.-W. Shu and S. Osher, J. Comput. Phys., 77 (1988), pp. 439-471] in this paper, which is based on interpolation for nodal values. The efficiency and good performance of our method are demonstrated by extensive numerical tests which indicate that the coordinate system of Riemann invariants is a good alternative of local characteristic fields for the WENO procedure. [ABSTRACT FROM AUTHOR]

This paper presents a fast high-order method for the solution of two-dimensional problems of scattering by penetrable inhomogeneous media, with application to high-frequency configurations containing (possibly) discontinuous refractivities. The method relies on a hybrid direct/iterative combination of (1) a differential volumetric formulation (which is based on the use of appropriate Chebyshev differentiation matrices enacting the Laplace operator) and (2) a secondkind boundary integral formulation (which, once again, utilizes Chebyshev discretization, but, in this case, in the boundary integral context). The approach enjoys low dispersion and high-order accuracy for smooth refractivities, as well as second-order accuracy (while maintaining low dispersion) in the discontinuous refractivity case. The solution approach proceeds by application of impedance-to-impedance (ItI) maps to couple the volumetric and boundary discretizations. The volumetric linear algebra solutions are obtained by means of a multifrontal solver, and the coupling with the boundary integral formulation is achieved via an application of the iterative linear algebra solver GMRES. In particular, the existence and uniqueness theory presented in the present paper provides an affirmative answer to an open question concerning the existence of a uniquely solvable second-kind ItI-based formulation for the overall scattering problem under consideration. Relying on a modestly demanding scatterer-dependent precomputation stage (requiring in practice a computing cost of the order of O(Nα ) operations, with α ≈ 1.07, for an N-point discretization and for the relevant Chebyshev accuracy orders q used), together with fast (O(N)-cost) single-core runs for each incident field considered, the proposed algorithm can effectively solve scattering problems for large and complex objects possibly containing discontinuities and strong refractivity contrasts. [ABSTRACT FROM AUTHOR]

This paper tackles efficient methods for Bayesian inverse problems with priors based on Whittle–Matérn Gaussian random fields. The Whittle–Matérn prior is characterized by a mean function and a covariance operator that is taken as a negative power of an elliptic differential operator. This approach is flexible in that it can incorporate a wide range of prior information including nonstationary effects, but it is currently computationally advantageous only for integer values of the exponent. In this paper, we derive an efficient method for handling all admissible noninteger values of the exponent. The method first discretizes the covariance operator using finite elements and quadrature, and uses preconditioned Krylov subspace solvers for shifted linear systems to efficiently apply the resulting covariance matrix to a vector. This approach can be used for generating samples from the distribution in two different ways: by solving a stochastic partial differential equation, and by using a truncated Karhunen–Loève expansion. We show how to incorporate this prior representation into the infinite-dimensional Bayesian formulation, and show how to efficiently compute the maximum a posteriori estimate, and approximate the posterior variance. Although the focus of this paper is on Bayesian inverse problems, the techniques developed here are applicable to solving systems with fractional Laplacians and Gaussian random fields. Numerical experiments demonstrate the performance and scalability of the solvers and their applicability to model and real-data inverse problems in tomography and a time-dependent heat equation. [ABSTRACT FROM AUTHOR]

In this paper, we propose a two-level block preconditioned Jacobi--Davidson (BPJD) method for efficiently solving discrete eigenvalue problems resulting from finite element approximations of 2mth (m= 1, 2) order symmetric elliptic eigenvalue problems. Our method works effectively to compute the first several eigenpairs, including both multiple and clustered eigenvalues with corresponding eigenfunctions, particularly. The method is highly parallelizable by constructing a new and efficient preconditioner using an overlapping domain decomposition (DD). It only requires computing a couple of small scale parallel subproblems and a quite small scale eigenvalue problem per iteration. Our theoretical analysis reveals that the convergence rate of the method is bounded by c(H)(1 C\delta 2m 1 H2m 1)2, where H is the diameter of subdomains and\delta is the overlapping size among subdomains. The constant C is independent of the mesh size h and the internal gaps among the target eigenvalues, demonstrating that our method is optimal and cluster robust. Meanwhile, the H-dependent constant c(H) decreases monotonically to 1, as H\rightarrow 0, which means that more subdomains lead to the better convergence rate. Numerical results supporting our theory are given. [ABSTRACT FROM AUTHOR]

This paper investigates the sampled-data stabilization of continuous-time probabilistic logical control networks (CT-PLCNs). CT-PLCNs can provide quantitative and accurate descriptions for the transient kinetics in comparing discrete-time probabilistic logical control networks (DT-PLCNs). First, CT-PLCNs are transformed into switched continuous-time probabilistic logical networks by regarding the control input as a switching signal. In this setup, CT-PLCNs can be classified into two types: one with stable modes and the other with only unstable modes. Then the concept of average l-sample dwell time is proposed to describe the scenario, where the dwell time of each mode is an integral multiple of the sampling period l. Based on this, the stabilization conditions for CT-PLCNs are established by restricting the sampling dwell time of controller modes. Furthermore, a copositive Lyapunov function is constructed for the case with stable modes and is discretized for the case without stable modes, providing a new framework for studying the stabilization of CT-PLCNs. Finally, a chemical model generated by GINsim is provided to demonstrate the feasibility of the obtained theoretical results. Overall, this paper provides new insights into the stabilization of CT-PLCNs and presents practical applications for chemical models. [ABSTRACT FROM AUTHOR]

This paper studies the linearization of the viscous tank--liquid system. The linearization of the tank--liquid system gives a high-order partial differential equation, which is a combination of a wave equation with Kelvin--Voigt damping and a Euler--Bernoulli beam equation. The single input appears in two of the boundary conditions (boundary input). The paper provides results both for the open-loop system (existence/uniqueness of solutions and stability properties of the open-loop system) as well as results for the construction of feedback stabilizers. More specifically, the feedback design methodology is based on control Lyapunov functionals (CLFs). The proposed CLFs are modifications and augmentations of the total energy functionals for the tank--liquid system so that the dissipative effects of viscosity, friction, and surface tension are captured. By focusing on the linearized water--tank system, we are able to provide results that are not provided in the nonlinear case: (1) existence and uniqueness of solutions, (2) simultaneous presence of friction and surface tension, and (3) stabilization in a stronger norm, using a different CLF. [ABSTRACT FROM AUTHOR]

This paper investigates a reversible investment problem with finite horizon, in which a social planner aims to determine the project's capacity level to minimize the expected total costs. These costs depend on the demand for the good, the supply in terms of production capacity, and the proportional costs. The issue of irreversible investment has been examined by Han and Yi [Commun. Nonlinear Sci. Numer. Simul., 109 (2022), 106302]. Mathematically, the reversible investment problem can be formulated as a singular stochastic control problem. The value function satisfies a two-dimensional parabolic variational inequality subject to gradient constraint, which leads to two time-dependent free boundaries representing optimal investment and disinvestment strategies. We employ a partial differential equation approach to characterize the continuity, monotonicity, and horizontal asymptotes of free boundaries, as well as establish the C2,1 regularity of the value function. To the best of our knowledge, the approach to analyze the behavior of free boundaries is novel in the literature. [ABSTRACT FROM AUTHOR]

We analyze the spectrum of the operator $\Delta{-1} [\nabla \cdot (K\nabla u)]$ subject to homogeneous Dirichlet or Neumann boundary conditions, where $\Delta$ denotes the Laplacian and $K=K(x,y)$ is a symmetric tensor. Our main result shows that this spectrum can be derived from the spectral decomposition $K=Q \Lambda QT$, where $Q=Q(x,y)$ is an orthogonal matrix and $\Lambda=\Lambda(x,y)$ is a diagonal matrix. More precisely, provided that $K$ is continuous, the spectrum equals the convex hull of the ranges of the diagonal function entries of $\Lambda$. The domain involved is assumed to be bounded and Lipschitz. In addition to studying operators defined on infinite-dimensional Sobolev spaces, we also report on recent results concerning their discretized finite-dimensional counterparts. More specifically, even though $\Delta{-1} [\nabla \cdot (K\nabla u)]$ is not compact, it turns out that every point in the spectrum of this operator can, to an arbitrary accuracy, be approximated by eigenvalues of the associated generalized algebraic eigenvalue problems arising from discretizations. Our theoretical investigations are illuminated by numerical experiments. The results presented in this paper extend previous analyses which have addressed elliptic differential operators with scalar coefficient functions. Our investigation is motivated by both preconditioning issues (efficient numerical computations) and the need to further develop the spectral theory of second order PDEs (core analysis). [ABSTRACT FROM AUTHOR]

The article introduces a new section structure for the SIAM Journal on Scientific Computing (SISC), including a focus on Scientific Machine Learning as a major development in the field of scientific computing. Topics include the development of accurate, efficient, and scalable machine learning algorithms for solving mathematical modeling problems, emphasizing the importance of reproducibility in the review process.

In the present paper, we prove convergence rates for the pressure of the local discontinuous Galerkin approximation, proposed in Part I of the paper [A. Kaltenbach and M. Růžička, SIAM J. Numer. Anal., 61 (2023), pp. 1613--1640], of systems of p-Navier-Stokes type and p-Stokes type with p ∈ (2,∞). The results are supported by numerical experiments. [ABSTRACT FROM AUTHOR]