Search

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 is focused on the approximation of the Euler equations of compressible fluid dynamics on a staggered mesh. With this aim, the flow parameters are described by the velocity, the density, and the internal energy. The thermodynamic quantities are described on the elements of the mesh, and thus the approximation is only in L2, while the kinematic quantities are globally continuous. The method is general in the sense that the thermodynamic and kinetic parameters are described by an arbitrary degree of polynomials. In practice, the difference between the degrees of the kinematic parameters and the thermodynamic ones is set to 1. The integration in time is done using the forward Euler method but can be extended straightforwardly to higher-order methods. In order to guarantee that the limit solution will be a weak solution of the problem, we introduce a general correction method in the spirit of the Lagrangian staggered method described in [R. Abgrall and S. Tokareva, SIAM J. Sci. Comput., 39 (2017), pp. A2345--A2364; R. Abgrall, K. Lipnikov, N. Morgan, and S. Tokareva, SIAM J. Sci. Comput., 2 (2020), pp. A343--A370; V. A. Dobrev, T. V. Kolev, and R. N. Rieben, SIAM J. Sci. Comput., 34 (2012), pp. B606--B641], and we prove a Lax--Wendroff theorem. The proof is valid for multidimensional versions of the scheme, even though most of the numerical illustrations in this work, on classical benchmark problems, are one-dimensional because we have easy access to the exact solution for comparison. We conclude by explaining that the method is general and can be used in different settings, for example, finite volume or discontinuous Galerkin method, not just the specific one presented in this paper. [ABSTRACT FROM AUTHOR]

The perfectly matched layer (PML) is a very popular tool in the truncation of wave scattering in unbounded domains. In [S. N. Chandler-Wilde and P. Monk, Appl. Numer. Math., 59 (2009), pp. 2131-2154], the author proposed a conjecture that for scattering problems with rough surfaces, the PML converges exponentially with respect to the PML parameter in any compact subset. In the author's previous paper [R. Zhang, SIAM J. Numer. Math., 60 (2022), pp. 804-823], this result has been proved for periodic surfaces in two-dimensional spaces, when the wave number is not a half-integer. In this paper, we prove that the method has a high-order convergence rate in the three-dimensional biperiodic surface scattering problems. We extend the two-dimensional results and prove that the exponential convergence still holds when the wave number is smaller than 0.5. For larger wave numbers, although exponential convergence is no longer proved, we are able to prove a higher-order convergence for the PML method. [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]

Entropy inequalities are crucial to the well-posedness of hyperbolic conservation laws, which help to select the physically meaningful one from among the infinite many weak solutions. Recently, several high order discontinuous Galerkin (DG) methods satisfying entropy inequalities were proposed; see [T. Chen and C.-W. Shu, J. Comput. Phys., 345 (2017), pp. 427-461; J. Chan, J. Comput. Phys., 362 (2018), pp. 346-374; T. Chen and C.-W. Shu, CSIAM Trans. Appl. Math., 1 (2020), pp. 1-52] and the references therein. However, high order numerical methods typically generate spurious oscillations in the presence of shock discontinuities. In this paper, we construct a high order entropy stable essentially oscillation-free DG (OFDG) method for hyperbolic conservation laws. With some suitable modification on the high order damping term introduced in [J. Lu, Y. Liu, and C.-W. Shu, SIAM J. Numer. Anal., 59 (2021), pp. 1299-1324; Y. Liu, J. Lu, and C.-W. Shu, SIAM J. Sci. Comput., 44 (2022), pp. A230-A259], we are able to construct an OFDG scheme with dissipative entropy. It is challenging to make the damping term compatible with the current entropy stable DG framework, that is, the damping term should be dissipative for any given entropy function without compromising high order accuracy. The key ingredient is to utilize the convexity of the entropy function and the orthogonality of the projection. Then the proposed method maintains the same properties of conservation, error estimates, and entropy dissipation as the original entropy stable DG method. Extensive numerical experiments are presented to validate the theoretical findings and the capability of controlling spurious oscillations of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The GMRES algorithm of Saad and Schultz [SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869] is an iterative method for approximately solving linear systems Ax = b, with initial guess x0 and residual r0 = b Ax0. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of Vκ). It is well known that this process can be viewed as a QR factorization of the matrix Bκ = [ r0, AVκ] at each iteration. Despite an O (ε)κ (Bκ) loss of orthogonality, for unit roundoff ε and condition number κ, the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. [SIAM J. Matrix Anal. Appl., 28 (2006), pp. 264-284]. We present an iterated Gauss-Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe [Linear Algebra Appl., 52 (1983), pp. 591-601] and Świrydowicz et al. [Numer. Linear Algebra Appl., 28 (2020), pp. 1-20]. IGS-GMRES maintains orthogonality to the level O (ε)κ (Bκ) or O (ε), depending on the choice of one or two iterations; for two Gauss-Seidel iterations, the computed Krylov basis vectors remain orthogonal to working accuracy and the smallest singular value of Vκ remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly nonnormal systems. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

This paper is the second of two articles, in which we aim to prove the convergence of the Hiptmair--Xu (HX) preconditioner (originally proposed by [R. Hiptmair and J. Xu, SIAM J. Numer. Anal., 45 (2007), pp. 2483--2509]) for H(curl)-elliptic boundary value problems with jump coefficients. In this paper, based on the auxiliary results obtained in our first article [Q. Hu, SIAM J. Numer. Anal., 59 (2021), pp. 2500--2535], we establish two new regular decompositions for lowdimensional edge finite element functions in three dimensions, which, under suitable assumptions on the distribution of the coefficients, are stable up to a polylogarithmic factor of the meshwidth with respect to weighted norms defined by the coefficients. Using these regular decompositions, we analyze the convergence of the HX preconditioner for the case of strongly discontinuous coefficients. We show that the HX preconditioner is asymptotically optimal up to a polylogarithmic factor in the meshwidth and is not severely affected by large jumps of the coefficients across the interface between two neighboring subdomains. [ABSTRACT FROM AUTHOR]

In this paper we revisit a two-level discretization based on localized orthogonal decomposition (LOD). It was originally proposed in [P. Henning, A. Målqvist, and D. Peterseim, SIAM J. Numer. Anal., 52 (2014), pp. 1525--1550] to compute ground states of Bose--Einstein condensates by finding discrete minimizers of the Gross--Pitaevskii energy functional. The established convergence rates for the method appeared, however, suboptimal compared to numerical observations and a proof of optimal rates in this setting remained open. In this paper we shall close this gap by proving optimal order error estimates for the L² - and H¹-errors between the exact ground state and discrete minimizers, as well as error estimates for the ground state energy and the ground state eigenvalue. In particular, the achieved convergence rates for the energy and the eigenvalue are of 6th order with respect to the mesh size on which the discrete LOD space is based, without making any additional regularity assumptions. These high rates justify the use of very coarse meshes, which significantly reduces the computational effort for finding accurate approximations of ground states. In addition, we include numerical experiments that confirm the optimality of the new theoretical convergence rates, for both smooth and discontinuous potentials. [ABSTRACT FROM AUTHOR]

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

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]

Part of the motivation of this paper comes from the recent paper [W. Guo and H.-Z. Zhou, SIAM J. Control Optim., 57 (2019), pp. 1890--1928], where an adaptive control approach was used to estimate in real time all amplitudes and phases of the external harmonic sinusoidal disturbance with known frequencies to achieve output regulation for a 1-d Euler--Bernoulli beam equation. In our paper, we change the landscape in a completely different way for the output regulation of the Euler--Bernoulli beam equation for which the disturbances are generated from a completely unknown finite-dimensional exosystem; i.e., the frequencies of the sinusoidal signals that appear in the reference signal and disturbances are completely unknown. In addition, the number of frequencies is also assumed to be unknown yet has a known upper bound. We apply the technique of the Sylvester equation to decouple the ODE of the exosystem and the PDE of the plant first, and then adopt the adaptive observer to estimate all possible unknown frequencies that have entered into the tracking error. By designing two different adaptive observers to estimate the unknown frequencies as well as the state of the plant and exosystem, we propose two tracking error based feedback controls for achieving output regulation for this PDE. [ABSTRACT FROM AUTHOR]

This paper concerns with the stabilizability for a quasilinear Klein-Gordon-wave system with variable coefficients in Rn. The stabilizability of linear wave-type equations with the Kelvin-Voigt damping has been considered by Liu-Zhang [SIAM J. Control Optim., 54 (2016), pp. 1859-1871] for an elastic string system, and by Yu-Han [SIAM J. Control Optim., 59 (2021), pp. 1973-1988] for the linear wave system in a cuboidal domain, respectively. In this paper, we establish that there exists a linear feedback control law such that the quasilinear Klein-Gordon-wave system is exponentially stable under certain smallness conditions, where the feedback control is a strong Kelvin-Voigt damping. [ABSTRACT FROM AUTHOR]

The object of this paper is the differentiation of the infimum of parametrized objective functions with respect to the parameters as in Danskin [SIAM J. Appl. Math., 14 (1966), pp. 641-664], who obtained a semidifferential equal to the infimum over the set of minimizers of the directional derivative with respect to the parameters. Yet, in applications to the topological and shape derivatives of the compliance, examples reveal the possible occurrence of an extra negative term: the so-called polarization term in Mechanics. The object of this paper is to introduce new theorems that can accommodate the occurrence of an extra term. For the shape derivative, the associated technique is a change of variable to work on the fixed initial domain; for the topological derivative, it is an extension over the hole created by the topological perturbation of the domain. [ABSTRACT FROM AUTHOR]

This paper proposes and analyzes a novel efficient high-order finite volume method for the ideal magnetohydrodynamics (MHD). As a distinctive feature, the method simultaneously preserves two critical physical constraints: a discretely divergence-free (DDF) constraint on the magnetic field and the positivity-preserving (PP) property, which ensures the positivity of density, pressure, and internal energy. To enforce the DDF condition in each cell, we design a new discrete projection approach that projects the reconstructed point values at the cell interface into a DDF space, without using any approximation polynomials. This projection method is highly efficient, easy to implement, and particularly suitable for the high-order finite volume methods that return only the point values (no explicit approximation polynomials) in the reconstruction. Moreover, we also develop a new finite volume framework for constructing provably PP schemes for the ideal MHD system. The framework comprises the discrete projection technique, a suitable approximation to the Godunov--Powell source terms, and a simple PP limiter. We provide rigorous analysis of the PP property of the proposed finite volume method, demonstrating that the DDF condition and the proper approximation to the source terms eliminate the impact of magnetic divergence terms on the PP property. The analysis is challenging due to the internal energy function's nonlinearity and the intricate relationship between the DDF and PP properties. To address these challenges, we adopt the recently developed geometric quasilinearization approach [K. Wu and C.-W. Shu, SIAM Rev., 65 (2023), pp. 1031--1073], which transforms a nonlinear constraint into a family of linear constraints. Finally, we validate the effectiveness of the proposed method through several benchmark and demanding numerical examples. The results demonstrate that the proposed method is robust, accurate, and highly effective, confirming the significance of the proposed DDF projection and PP techniques. [ABSTRACT FROM AUTHOR]

The separation of two sets (or more specific of two cones) plays an important role in different fields of mathematics such as variational analysis, convex analysis, convex geometry, and optimization. In the paper, we derive some new results for the separation of two not necessarily convex cones by a (convex) cone/conical surface in real (topological) linear spaces. Basically, we follow the separation approach by Kasimbeyli [SIAM J. Optim., 20 (2010), pp. 1591-1619] based on augmented dual cones and Bishop--Phelps type (normlinear) separating functions. Classical separation theorems for convex sets are the key tool for proving our main nonlinear cone separation theorems. [ABSTRACT FROM AUTHOR]

We present a linear algebra formulation of backpropagation which allows the calculation of gradients by using a generically written "backslash"" or Gaussian elimination on triangular systems of equations. Generally, the matrix elements are operators. This paper has three contributions: (i) it is of intellectual value to replace traditional treatments of automatic differentiation with a (left acting) operator theoretic, graph-based approach; (ii) operators can be readily placed in matrices in software in programming languages such as Julia as an implementation option; (iii) we introduce a novel notation, "transpose dot"" operator "T." that allows for the reversal of operators. We further demonstrate the elegance of the operators approach in a suitable programming language consisting of generic linear algebra operators such as Julia [Bezanson et al., SIAM Rev., 59 (2017), pp. 65--98], and that it is possible to realize this abstraction in code. Our implementation shows how generic linear algebra can allow operators as elements of matrices. In contrast to "operator overloading,"" where backslash would normally have to be rewritten to take advantage of operators, with "generic programming"" there is no such need. [ABSTRACT FROM AUTHOR]

In this paper, we study the stabilization issue for a multidimensional wave equation with localized Kelvin--Voigt damping on a cuboidal domain, in which the damping region does not satisfy the geometric control condition (GCC). The variable damping coefficient is assumed to be degenerate near the interface. We prove that the system is polynomially stable with a decay rate depending on the degree of the degeneration γ. A relationship between the decay order and γ is identified. In particular, this decay rate is consistent with the optimal one for the corresponding system with constant damping coefficient (i.e., γ = 0) obtained in [K. Yu and Z.-J. Han, SIAM J. Control Optim., 59 (2021), pp. 1973--1988]. Moreover, it is the first result on the decay rates of the solutions to multidimensional wave equations with localized degenerate Kelvin--Voigt damping when GCC is not satisfied. [ABSTRACT FROM AUTHOR]

There are three different forms of adjoint inclusions that appear in the most advanced necessary optimality conditions for optimal control problems involving differential inclusions: Euler--Lagrange inclusion (with partial convexification) [A. D. Ioffe, J. Optim. Theory Appl., 182 (2019), pp. 285--309], fully convexified Hamiltonian inclusion [F. H. Clarke, Mem. Amer. Math. Soc., 173 (2005), 816], and partially convexified Hamiltonian inclusion [P. D. Loewen and R. T. Rockafellar, SIAM J. Control Optim., 34 (1996), pp. 1496--1511], [A. D. Ioffe, Trans. Amer. Math. Soc., 349 (1997), pp. 2871--2900], [R. B. Vinter, SIAM J. Control Optim., 52 (2014), pp. 1237--1250] (for convex-valued differential inclusions in the first two references). This paper addresses all three types of necessary conditions for problems with (in general) nonconvex-valued differential inclusions. The first of the two main theorems, with the Euler--Lagrange inclusion, is equivalent to the main result of [A. D. Ioffe, J. Optim. Theory Appl., 182 (2019), pp. 285--309] but proved in a substantially different and much more direct way. The second theorem contains conditions that guarantee necessity of both types of Hamiltonian conditions. It seems to be the first result of such a sort that covers differential inclusions with possibly unbounded values and contains the most recent results of [F. H. Clarke, Mem. Amer. Math. Soc., 173 (2005), 816] and [R. B. Vinter, SIAM J. Control Optim., 52 (2014), pp. 1237--1250] as particular cases. And again, the proof of the theorem is based on a substantially different approach. [ABSTRACT FROM AUTHOR]

A remarkable conjecture of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] asserts that for any collection of n independent nonnegative, where X = Σ ni=1=i. In this paper, we investigate thisconjecture for the class of discrete log-concave probability distributions, and we prove a strengthened version. More specifically, we show that the conjectured bound 1/e holds when Xi's are independent discrete log-concave with arbitrary expectation. [ABSTRACT FROM AUTHOR]

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a "small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in a running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a "random looking" graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t). nc, where f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in n (i.e., n (1)). In particular, given constants d > c 1, we output a bipartite graph that has n left nodes and nc right nodes with right-degree of d so that any right set of size at most n (1) expands by factor of (d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and lowdensity parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [SIAM J. Comput., 36 (2006), pp. 845-888] and Ishai et al. [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433-442]). [ABSTRACT FROM AUTHOR]

In the Bin Packing problem one is given n items with weights w(1),. . . ,w(n) and m bins with capacities c1, . . ., cm. The goal is to partition the items into sets S1, . . . ,Sm such that w(Sj 0 such that an instance of Bin Packing with m bins can be solved in O (2(1 y m)n) randomized time. Before our work, such improved algorithms were not known even for m= 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset Σ: For every γ > 0 there exists an >0 such that if | { X n{ 1, . . . ,n}: w(X) =v} | 2(1)n for some v, then { w(X) :X { 1, . . . ,n\} | &#947n. [ABSTRACT FROM AUTHOR]

In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min\{ O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537--550]. In this paper we consider the low-frequency range, when f =O(log n), and obtain deterministic algorithms with a (1 + \epsilon)f-approximation ratio and the following guarantees on the update time. (1) O((f/\epsilon) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1+\epsilon)f-approximation algorithm with O((f2/\epsilon) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon 3 + (f/\epsilon 2) \cdot logC \bigr) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f =o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon)-approximate minimum vertex cover in O(1/\epsilon 2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon 3) \cdot log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3 n/\sansp \sanso \sansl \sansy (\epsilon)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C = 1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470--489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds. [ABSTRACT FROM AUTHOR]

For a fixed "pattern" graph G, the colored G-subgraph isomorphism problem (denoted by SUB(G)) asks, given an n-vertex graph H and a coloring V (H) → V (G), whether H contains a properly colored copy of G. The complexity of this problem is tied to parameterized versions of P =? NP and L =? NL, among other questions. An overarching goal is to understand the complexity of SUB(G), under different computational models, in terms of natural invariants of the pattern graph G. In this paper, we establish a close relationship between the formula complexity of SUB(G) and an invariant known as tree-depth (denoted by\sanst \sansd (G)). SUB(G) is known to be solvable by monotone AC0 formulas of size O(ntd(G)). Our main result is an nΩtd (G)1/3) lower bound for formulas that are monotone or have sublogarithmic depth. This complements a lower bound of Li, Razborov, and Rossman [SIAM J. Comput., 46 (2017), pp. 936--971] relating tree-width and AC0 circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for firstorder logic on finite structures [B. Rossman, An improved homomorphism preservation theorem from lower bounds in circuit complexity, in 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 27]. The technical core of this result is an nΩ (k) lower bound in the special case where G is a complete binary tree of height k, which we establish using the pathset framework introduced in B. Rossman [SIAM J. Comput., 47 (2018), pp. 1986--2028]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [W. Czerwi, W. Nadara, and M. Pilipczuk, SIAM J. Discrete Math., 35 (2021), pp. 934--947; K. Kawarabayashi and B. Rossman, A polynomial excluded-minor approximation of treedepth, in Proceedings of the 2018 Annual ACMSIAM Symposium on Discrete Algorithms, 2018, pp. 234--246]. Additional results of this paper extend the pathset framework and improve upon both the best known upper and lower bounds on the average-case formula size of SUB(G) when G is a path. [ABSTRACT FROM AUTHOR]

This corrigendum provides a variant of the Brondsted-Rockafellar theorem, which helps to correct an error in the proof of the sufficiency part of Theorem 2.8 in [X. Y. Zheng, SIAM J. Optim., 33 (2023), pp. 338-359] and to establish the correct characterization for a closed convex set to be Cp-differentiable. In particular, in the original paper, Theorem 2.8 holds with εp 1+p replacing εp2, and Theorem 3.2 holds with "1+pp-order-well-posed solvable" replacing"2 p -order-well-posed solvable." All other results remain true. [ABSTRACT FROM AUTHOR]

This paper is concerned with ℓq (0

This paper studies an optimization problem on the sum of traces of matrix quadratic forms in m semiorthogonal matrices, which can be considered as a generalization of the synchronization of rotations. While the problem is nonconvex, this paper shows that its semidefinite pro-gramming relaxation solves the original nonconvex problems exactly with high probability under an additive noise model with small noise in the order of O(m1/4). In addition, it shows that, with high probability, the sufficient condition for global optimality considered in Won, Zhou, and Lange [SIAM J. Matrix Anal. Appl., 2 (2021), pp. 859-882] is also necessary under a similar small noise condition. These results can be considered as a generalization of existing results on phase synchronization. [ABSTRACT FROM AUTHOR]

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] for packing/covering linear programs. [ABSTRACT FROM AUTHOR]

In this paper, we focus our investigation on providing long-term estimates of the Hamiltonian deviation computed along numerical approximations to the solutions of stochastic Hamiltonian systems, of both It\and Stratonovich types. It is well known that the expected Hamiltonian of an It Hamiltonian system with additive noise exhibits a linear drift in time [C. Chen et al., Adv. Comput. Math., 46 (2020), 27], while the Hamiltonian function is conserved along the exact flow of a Stratonovich Hamiltonian system [T. Misawa, Japan J. Indust. Appl. Math., 17 (2000), pp. 119--128; T. Misawa, Math. Probl. Eng., 2010 (2010), 384937]. Here, we focus our attention on providing modified differential equations associated to suitable discretizations for the above problems, by means of weak backward error analysis arguments [K. C. Zygalakis, SIAM J. Sci. Comput., 33 (2011), pp. 102--130]. Then, long-term estimates are provided for both It and Stratonovich Hamiltonian systems, revealing the presence of parasitic terms affecting the overall conservation accuracy. Finally, selected numerical experiments are provided to confirm the theoretical analysis. [ABSTRACT FROM AUTHOR]

Computing the strongly connected Components (SCCs) in a graph G = (V, E) is known to take only O(m+n) time using an algorithm by Tarjan [SIAM J. Comput., 1 (1972), pp. 146-- 160] where m = | E|, n = | V | . For fully dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e., graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time O\~(m), thus only a polylogarithmic factor from the optimal running time. (We use O\~(f(n)) notation to suppress logarithmic factors, i.e., g(n) = O\~(f(n)) if g(n) = O(f(n)polylog(n)).) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs S \times V, S \subseteq V in fully dynamic graphs with update time O\~( | S| m t ) and query time O(t) for all t \in [1, | S| ]; this matches to polylogarithmic factors the best all-pairs reachability algorithm for S = V . [ABSTRACT FROM AUTHOR]

In neuroscience, synaptic plasticity refers to the set of mechanisms driving the dynamics of neuronal connections, called synapses and represented by a scalar value, the synaptic weight. A spike-timing-dependent plasticity (STDP) rule is a biologically based model representing the time evolution of the synaptic weight as a functional of the past spiking activity of adjacent neurons. A general mathematical framework has been introduced in [P. Robert and G. Vignoud, SIAM. J. Appl. Math., 81 (2021), pp. 1821-1846]. In this paper, we develop and investigate a scaling approach of these models based on several biological assumptions. Experiments show that long-term synaptic plasticity evolves on a much slower timescale than the cellular mechanisms driving the activity of neuronal cells, like their spiking activity or the concentration of various chemical components created/suppressed by this spiking activity. For this reason, a scaled version of the stochastic model of Robert and Vignoud [SIAM. J. Appl. Math., 81 (2021), pp. 1821-1846] is introduced and a limit theorem, an averaging principle, is stated for a large class of plasticity kernels. A companion paper [P. Robert and G. Vignoud, J. Stat. Phys. 183 (2021), 47] is entirely devoted to the tightness properties used to prove these convergence results. These averaging principles are used to study two important STDP models: pair-based rules and calcium-based rules. Our results are compared with the approximations of neuroscience STDP models. A class of discrete models of STDP rules is also investigated for the analytical tractability of its limiting dynamical system. [ABSTRACT FROM AUTHOR]

Given a closed convex set A in a Banach space X, motivated by the continuity and Fréchet differentiability of A introduced, respectively, in [D. Gale and V. Klee, Math. Scand., 7 (1959), pp. 379-391] and [X. Y. Zheng, SIAM J. Optim., 30 (2020), pp. 490-512], this paper considers the Cp-differentiability, subdifferentiability, and G\^ateaux differentiability of A. Using the technique of variational analysis, it is proved that A is Cp-differentiable (resp., subdifferentiable or G\^ateaux differentiable) if and only if for every continuous convex function f : X → R with infx∈A f(x) > infx∈X f(x) the corresponding constrained optimization problem PA(f) is 2/p-order-well-posed solvable (resp., generalized well-posed solvable or weak well-posed solvable). It is also proved that if the conjugate function f* of a continuous convex function f on X is Cp-differentiable on dom(f*), then for every closed convex set A in X with infx∈A f(x) > -∞ the corresponding optimization problem PA(f) is 2/p-order-well-posed solvable. As a byproduct, every constrained convex optimization problem with a strongly convex quadratic objective function is proved to be globally second-order-well-posed solvable. Our main results are new even in the case of finite dimensional spaces. [ABSTRACT FROM AUTHOR]

In the numerical simulation of ideal magnetohydrodynamics (MHD), keeping the pressure and density always positive is essential for both physical considerations and numerical stability. This is however a challenging task, due to the underlying relation between such a positivity-preserving (PP) property and the magnetic divergence-free (DF) constraint as well as the strong nonlinearity of the MHD equations. In this paper, we present the first rigorous PP analysis of the central discontinuous Galerkin (CDG) methods and construct arbitrarily high-order provably PP CDG schemes for ideal MHD. By the recently developed geometric quasilinearization (GQL) approach, our analysis reveals that the PP property of standard CDG methods is closely related to a discrete magnetic DF condition, whose form was unknown prior to our analysis and differs from that for the noncentral discontinuous Galerkin (DG) and finite volume methods in [K. Wu, SIAM J. Numer. Anal., 56 (2018), pp. 2124-2147]. The discovery of this relation lays the foundation for the design of our PP CDG schemes. In the one-dimensional (1D) case, the discrete DF condition is naturally satisfied, and we rigorously prove that the standard CDG method is PP under a condition that can be enforced easily with an existing PP limiter. However, in the multidimensional cases, the corresponding discrete DF condition is highly nontrivial, yet critical, and we analytically prove that the standard CDG method, even with the PP limiter, is not PP in general, as it generally fails to meet the discrete DF condition. We address this issue by carefully analyzing the structure of the discrete divergence terms and then constructing new locally DF CDG schemes for Godunov's modified MHD equations with an additional source term. The key point is to find out the suitable discretization of the source term such that it exactly cancels out all the terms in the discovered discrete DF condition. Based on the GQL approach, we prove in theory the PP property of the new multidimensional CDG schemes under a CFL condition. The robustness and accuracy of the proposed PP CDG schemes are further validated by several demanding 1D, two-dimensional, and three-dimensional numerical MHD examples, including the high-speed jets and blast problems with very low plasma beta. [ABSTRACT FROM AUTHOR]

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

In this paper, we investigate representations of links that are either centrally symmetric in R3 or antipodally symmetric in S3. By using the notions of antipodally self-dual and antipodally symmetric maps, introduced and studied by the authors in [L. Montejano, J. L. Ramírez Alfonsín, and I. Rasskin, SIAM J. Discrete Math., 36 (2022), pp. 1551-1566], we are able to present sufficient combinatorial conditions for a link L to admit such representations. The latter naturally provide sufficient conditions for L to be amphichiral. We also introduce another (closely related) method yielding again sufficient conditions for L to be amphichiral. We finally prove that a link L, associated to a map G, is amphichiral if the self-dual pairing of G is not one of 6 specific cases among the classification of the 24 self-dual pairing Cor(G)⊳Aut(G). [ABSTRACT FROM AUTHOR]

We consider the nonlinear Neumann problem for fully nonlinear elliptic PDEs on a quadrant. We establish a comparison theorem for viscosity sub- and supersolutions of the nonlinear Neumann problem. The crucial argument in the proof of the comparison theorem is to build a C1,1 test function which takes care of the nonlinear Neumann boundary condition. A similar problem has been treated on a general n-dimensional orthant by Biswas et al. [SIAM J. Control Optim., 55 (2017), pp. 365-396], where the functions (Hi in the main text) describing the boundary condition are required to be positively one-homogeneous, and the result in this paper removes the positive homogeneity in two dimensions. An existence result for solutions is also presented. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a mass-spring-friction oscillator with the friction modeled by a regularized stiction model. We do so in the limit where the ratio of the natural spring frequency and the forcing frequency is on the same order of magnitude as the scale associated with the regularized stiction model. The motivation for studying this special parameter regime (which can be interpreted as a rigid body limit) comes from [E. Bossolini, M. Br{\e}ns, and K. U. Kristiansen, SIAM J. Appl. Dyn. Syst., 16, (2017), pp. 2233-2258] which demonstrated new friction phenomena in this regime. The results of this paper led to some open problems; see also [E. Bossolini, M. Br{\e}ns, and K. U. Kristiansen, SIAM Rev., 62 (2020), pp. 869-897], that we resolve in this paper. In particular, using GSPT and blowup [C. K. R. T. Jones, in Dynamical Systems, Lecture Notes in Math. 1609, Springer, Berlin, 1995, pp. 44-118; M. Krupa and P. Szmolyan, SIAM J. Math. Anal., 33, (2001), pp. 286-314], we provide a simple geometric description of the bifurcation of stick-slip limit cycles through a combination of a canard and a global return mechanism. We also show that this combination leads to a canard-based horseshoe and are therefore able to prove existence of chaos in this fundamental oscillator system. [ABSTRACT FROM AUTHOR]

This paper is the first in a series of two articles, aiming to prove the convergence of the HX preconditioner originally proposed by Hiptmair and Xu [SIAM J. Numer. Anal., 45 (2007), pp. 2483-2509] for Maxwell's equations with jump coefficients. In this paper, we establish several extensions of the discrete regular decomposition for edge finite element functions defined in threedimensional domains. The functions defined by the new discrete regular decompositions can inherit zero degrees of freedom of the considered edge finite element function on some faces and edges of polyhedral domains as well as of some non-Lipschitz domains and possess nearly optimal stability with only a logarithmic factor. [ABSTRACT FROM AUTHOR]

This paper builds on the algebraic theory in the companion paper [S. F. McCormick, J. Benzaken, and R. Tamstorf, SIAM J. Sci. Comput., 43 (2021), pp. S392--S419] to obtain discretization-error-accurate solutions for linear elliptic partial differential equations (PDEs) by mixed-precision multigrid solvers. It is often assumed that the achievable accuracy is limited by discretization or algebraic errors. On the contrary, we show that the quantization error incurred by simply storing the matrix in any fixed precision quickly begins to dominate the total error as the discretization is refined. We extend the existing theory to account for these quantization errors and use the resulting bounds to guide the choice of four different precision levels in order to balance quantization, algebraic, and discretization errors in the progressive-precision scheme proposed in the companion paper. A remarkable result is that while iterative refinement is susceptible to quantization errors during the residual and update computations, the V-cycle used to compute the correction in each iteration is much more resilient and continues to work if the system matrices in the hierarchy become indefinite due to quantization. As a result, the V-cycle only requires relatively few bits of precision per level. Based on our findings, we outline a simple way to implement a progressive-precision full multigrid (FMG) solver with minimal overhead and demonstrate as an example that the one-dimensional biharmonic equation can be solved reliably to any desired accuracy using just a few V-cycles when the underlying smoother works well. Additionally, we show that the progressive-precision scheme leads to memory savings of up to 50\% compared to fixed precision. [ABSTRACT FROM AUTHOR]

In this paper, we adopt the augmented Lagrangian method (ALM) to solve convex quadratic second-order cone programming problems (SOCPs). Fruitful results on the efficiency of the ALM have been established in the literature. Recently, it has been shown in [Cui, Sun, and Toh, Math. Program., 178 (2019), pp. 381-415] that if the quadratic growth condition holds at an optimal solution for the dual problem, then the KKT residual converges to zero R-superlinearly when the ALM is applied to the primal problem. Moreover, Cui, Ding, and Zhao [SIAM J. 0ptim., 27 (2017), pp. 2332-2355] provided sufficient conditions for the quadratic growth condition to hold under the metric subregularity and bounded linear regularity conditions for solving composite matrix optimization problems involving spectral functions. Here, we adopt these recent ideas to analyze the convergence properties of the ALM when applied to SOCPs. To the best of our knowledge, no similar work has been done for SOCPs so far. In our paper, we first provide sufficient conditions to ensure the quadratic growth condition for SOCPs. With these elegant theoretical guarantees, we then design an SOCP solver and apply it to solve various classes of SOCPs, such as minimal enclosing ball problems, classical trust-region subproblems, square-root Lasso problems, and DIMACS Challenge problems. Numerical results show that the proposed ALM based solver is efficient and robust compared to the existing highly developed solvers, such as Mosek and SDPT3. [ABSTRACT FROM AUTHOR]

We correct assumption (4.6) in Theorem 4.1 in [F. Gozzi and F. Masiero, SIAM J. Control Optim., 55 (2017), pp. 2981-3012], and we consequently change the proof of Theorem 4.1. We correct the proof of Lemma 5.4 in [F. Gozzi and F. Masiero, SIAM J. Control Optim., 55 (2017), pp. 2981-3012]. Moreover, throughout the paper, starting from formulas (3.13) and (3.14), we notice that the current cost of the control problem cannot depend on the state for the results of the paper to work. This change in the current cost must be made in the paper [F. Gozzi and F. Masiero, SIAM J. Control Optim., 55 (2017), pp. 3013-3038], too. [ABSTRACT FROM AUTHOR]

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

A general adaptive refinement strategy for solving linear elliptic partial differential equations with random data is proposed and analysed herein. The adaptive strategy extends the a posteriori error estimation framework introduced by Guignard and Nobile [SIAM J. Numer. Anal., 56 (2018), pp. 3121-3143] to cover problems with a nonaffine parametric coefficient dependence. A suboptimal, but nonetheless reliable and convenient implementation of the strategy involves aproximation of the decoupled PDE problems with a common finite element approximation space. Computational results obtained using such a single-level strategy are presented in this paper (part I). Results obtained using a potentially more efficient multilevel approximation strategy, where meshes are individually tailored, will be discussed in part II of this work. The codes used to generate the numerical results are available on GitHub. [ABSTRACT FROM AUTHOR]

In this paper we consider the numerical solution of second-order semilinear differential equations for which the stiffness is induced by only a few components of the linear part. For such problems, the leapfrog scheme suffers from severe restrictions on the step size to ensure stability. We thus propose a general class of multirate leapfrog-type methods which allows one to use step sizes which are independent of the stiff part of the equation and also very efficient to implement. The methods are constructed by combining the leapfrog scheme with an explicit scheme with a larger stability region, an implicit scheme, or a trigonometric integrator. For spatially discretized partial differential equations, this class comprises local time-stepping schemes [J. Diaz and M. J. Grote, SIAM J. Sci. Comput., 31 (2009), pp. 1985--2014], [M. Grote, S. Michel, and S. Sauter, Math. Comp., 90 (2021), pp. 2603--2643] but also locally implicit or locally trigonometric integrators. Our main contribution is a rigorous error and stability analysis for the whole class of methods. Special emphasis is taken for explicit multirate methods, which are based on stabilized leapfrog-Chebyshev polynomials introduced in [C. Carle, M. Hochbruck, and A. Sturm, SIAM J. Numer. Anal., 58 (2020), pp. 2404--2433] as well as implicit/explicit (IMEX) methods based on 0-schemes. [ABSTRACT FROM AUTHOR]

This paper presents a systematic theoretical framework to derive the energy identities of general implicit and explicit Runge--Kutta (RK) methods for linear seminegative systems. It generalizes the stability analysis of only explicit RK methods in [Z. Sun and C.-W. Shu, SIAM J. Numer. Anal., 57 (2019), pp. 1158--1182]. The established energy identities provide a precise characterization on whether and how the energy dissipates in the RK discretization, thereby leading to weak and strong stability criteria of RK methods. Furthermore, we discover a unified energy identity for all the diagonal Pad\'e approximations, based on an analytical Cholesky type decomposition of a class of symmetric matrices. The structure of the matrices is very complicated, rendering the discovery of the unified energy identity and the proof of the decomposition highly challenging. Our proofs involve the construction of technical combinatorial identities and novel techniques from the theory of hypergeometric series. Our framework is motivated by a discrete analogue of integration by parts technique and a series expansion of the continuous energy law. In some special cases, our analyses establish a close connection between the continuous and discrete energy laws, enhancing our understanding of their intrinsic mechanisms. Several specific examples of implicit methods are given to illustrate the discrete energy laws. A few numerical examples further confirm the theoretical properties. [ABSTRACT FROM AUTHOR]

The purpose of this note is to correct mistakes and inaccuracies in technical claims in [Y. Rabani and A. Shpilka, SIAM J. Comput., 39 (2010), pp. 3501{3520]. These have no effect on the main results in the paper. [ABSTRACT FROM AUTHOR]

Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of ℓ1 and ℓ2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing ℓ1/ℓ2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka--Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the ℓ1/ℓ2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell 2 norm or Lorentzian norm via solving the corresponding ℓ1/ℓ2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy. [ABSTRACT FROM AUTHOR]

n the article "A Rational QZ Method" by D. Camps, K. Meerbergen, and R. Vande-bril [SIAM J. Matrix Anal. Appl., 40 (2019), pp. 943--972], we introduced rational QZ (RQZ) methods. Our theoretical examinations revealed that the convergence of the RQZ method is governed by rational subspace iteration, thereby generalizing the classical QZ method, whose convergence relieson polynomial subspace iteration. Moreover the RQZ method operates on a pencil more general than Hessenberg---upper triangular, namely, a Hessenberg pencil, which is a pencil consisting of two Hessenberg matrices. However, the RQZ method can only be made competitive to advanced QZ implementations by using crucial add-ons such as small bulge multi shift sweeps, aggressive early deflation, and optimal packing. In this paper we develop these techniques for the RQZ method.In the numerical experiments we compare the results with state-of-the-art routines for the generalized eigenvalue problem and show that the presented method is competitive in terms of speed and accuracy. [ABSTRACT FROM AUTHOR]

This paper proposes some efficient and accurate adaptive two-grid (ATG) finite element algorithms for linear and nonlinear PDEs. The main idea of these algorithms is to utilize the solutions on the kth-level adaptive meshes to find the solutions on the (k + 1)th-level adaptive meshes which are constructed by performing adaptive element bisections on the k th-level adaptive meshes. These algorithms transform nonsymmetric positive definite (non-SPD) PDEs (resp., nonlinear PDEs) into symmetric positive definite (SPD) PDEs (resp., linear PDEs). The proposed algorithms are both accurate and efficient due to the following advantages: They do not need to solve the nonsymmetric or nonlinear systems; the degrees of freedom are very small, they are easily implemented, and the interpolation errors are very small. Next, this paper constructs residual-type a posteriori error estimators which are shown to be reliable and efficient. The key ingredient in proving the efficiency is to establish an upper bound of the oscillation terms, which may not be higher-order terms due to the low regularity of the numerical solution. Furthermore, the convergence of the algorithms is proved when bisection is used for the mesh refinements. Finally, numerical experiments are provided to verify the accuracy and efficiency of the ATG finite element algorithms compared to regular adaptive finite element algorithms and two-grid finite element algorithms [J. Xu, SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777]. [ABSTRACT FROM AUTHOR]

In this paper, we resolve the one-pass space complexity of perfect Lp sampling for p ∈ (0, 2) in a stream. Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ ℝn, a perfect Lp sampler must output an index i with probability |fi|p/∥ f∥pp and is allowed to fail with some probability δ. So far, for p > 0 no algorithm has been shown to solve the problem exactly using poly(log n)-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate Lp sampler which, given an approximation parameter ν, outputs i with probability (1±ν)|fi| p/∥f∥pp, using space polynomial in ν-1 and log(n). The space complexity was later reduced by Jowhari, Sağlam, and Tardos to roughly O(ν-p log² n log δ-1) for p ∈ (0, 2), which matches the general p ≥ 0 lower bound of Ω (log² n log δ-1) in terms of n and δ, but is loose in terms of ν. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of ν---not even a bound of Ω (ν-1) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log² n log δ-1)-bit perfect Lp sampler for p ∈ (0, 2). This shows that ν need not factor into the space of an Lp sampler, which closes the complexity of the problem for this range of p. For p = 2, our bound is O(log³ n log δ-1)-bits, which matches the prior best known upper bound of O(ν-2 log³ n log δ-1), but has no dependence on ν. Note that there is still a log n gap between our upper bound and the lower bound for p = 2, the ution of which we leave as an open problem. For p < 2, our bound holds in the random oracle model, matching the lower bounds in that model. However, we show that our algorithm can be derandomized with only a O((log log n)²) blow-up in the space (and no blow-up for p = 2). Our derandomization technique is quite general, and can be used to derandomize a large class of linear sketches, including the more accurate count-sketch variant of Minton and Price [Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 669-686], resolving an open question in that paper. Finally, we show that a (1 ± ∈) relative error estimate of the frequency fi of the sampled index i can be obtained using an additional O(∈-p log n)-bits of space for p < 2, and O(∈-2 log² n) bits for p = 2, which was possible before only by running the prior algorithms with ν = ∈. [ABSTRACT FROM AUTHOR]