Search

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]

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]

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]

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]

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]

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 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]

This paper is devoted to the development and convergence analysis of greedy reconstruction algorithms based on the strategy presented in [Y. Maday and J. Salomon, Joint Proceedings of the 48th IEEE Conference on Decision and Control and the 28th Chinese Control Conference, 2009, pp. 375--379]. These procedures allow the design of a sequence of control functions that ease the identification of unknown operators in nonlinear dynamical systems. The original strategy of greedy reconstruction algorithms is based on an offline/online decomposition of the reconstruction process and an ansatz for the unknown operator obtained by an a priori chosen set of linearly independent matrices. In the previous work [S. Buchwald, G. Ciaramella, and J. Salomon, SIAM J. Control Optim., 59 (2021), pp. 4511--4537], convergence results were obtained in the case of linear identification problems. We tackle here the more general case of nonlinear systems. More precisely, we introduce a new greedy algorithm based on the linearized system. We show that the controls obtained with this new algorithm lead to the local convergence of the classical Gauss--Newton method applied to the online nonlinear identification problem. We then extend this result to the controls obtained on nonlinear systems where a local convergence result is also proved. The main convergence results are obtained for dynamical systems with linear and bilinear control structures. [ABSTRACT FROM AUTHOR]

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

In this paper, we propose an efficient sieving-based secant method to address the computational challenges of solving sparse optimization problems with least-squares constraints. A level-set method has been introduced in [X. Li, D. F. Sun, and K.-C. Toh, SIAM J. Optim., 28 (2018), pp. 1842-1866] that solves these problems by using the bisection method to find a root of a univariate nonsmooth equation varphi (λ) =varrho for some varrho >0, where varphi (·) is the value function computed by a solution of the corresponding regularized least-squares optimization problem. When the objective function in the constrained problem is a polyhedral gauge function, we prove that (i) for any positive integer k, varphi (·) is piecewise Ck in an open interval containing the solution λ ast to the equation varphi (λ) =varrho and that (ii) the Clarke Jacobian of varphi (·) is always positive. These results allow us to establish the essential ingredients of the fast convergence rates of the secant method. Moreover, an adaptive sieving technique is incorporated into the secant method to effectively reduce the dimension of the level-set subproblems for computing the value of varphi (·). The high efficiency of the proposed algorithm is demonstrated by extensive numerical results. [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 a recent paper [T. Batard, G. Haro, and C. Ballester, SIAM J. Imag. Sci., 14 (2021), pp. 1816-1847], a new prior for image restoration was introduced. It relies first on the observation that an image and a degraded version of it can share some visual content and then on the conjecture that an image restoration model can benefit from the use of an image prior encoding this invariance property. This prior considers the restored image as a parallel section of a connection (also called covariant derivative), this latter being a critical point of an energy associated to the Lie group R+*× SO(2) acting on image pixel values. In this paper, we propose a twofold generalization of this result. First, we consider other Lie groups acting on image pixels, yielding new optimal connections. Then, we derive a family of α -connections from the optimal connections. The corresponding parallel sections describe new invariance properties which we use as priors encoded as penalty terms in variational models for image restoration. Experiments conducted on color image deblurring show that the proposed generalization of the work of Batard, Haro, and Ballester outperforms the original approach. [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]

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]

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 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]

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]

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]

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]

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]

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 note indicates an error in the proof of Theorem 3.1 in [T. Vidick, SIAM J. Comput., 45 (2016), pp. 1007--1063]. Due to an induction step in the soundness analysis not being carried out correctly, the analysis fails to prove the claimed result. The error invalidates the proofs of the main computational hardness results claimed in the paper. We discuss implications for subsequent works. In some cases results can be partially recovered by applying a weakened version of Theorem 3.1 shown in [Z. Ji et al., Quantum Soundness of the Classical Low Individual Degree Test, arXiv:2009.1298, 2020] subsequently to the discovery of the error. The validity of Theorem 3.1 as stated in the paper remains an open question. [ABSTRACT FROM AUTHOR]

A typo in the paper [M. Hladík, SIAM J. Matrix Anal. Appl., 44 (2023), pp. 175-195] is corrected. [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]

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]

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(Sjmn) notation omits factors polynomial in the input size). In this paper, we show that for every m N there exists a constant Σm > 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]

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]

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]

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]

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]

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

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]

This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [I. Ekren, et al., Ann. Probab., 42 (2014), pp. 204-236], which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions and reduces to the notion of stochastic viscosity solutions analyzed in [E. Bayraktar and M. Sirbu, Proc. Amer. Math. Soc., 140 (2012), pp. 3645-3654; SIAM J. Control Optim., 51 (2013), pp. 4274-4294]. Our main result takes advantage of this enlargement of the test functions and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [L. A. Caffarelli and X. Cabre, Amer. Math. Soc. Colloq. Publ., 43, AMS, Providence, RI, 1995], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [I. Ekren et al., Ann. Probab., 42 (2014), pp. 204-236]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution. [ABSTRACT FROM AUTHOR]

In the original article [B. Jacob et al., SIAM J. Control Optim., 58 (2020), pp. 2952-2978] an unfortunate mistake appears in the definition of "norm-to-integral ISS." As the paper was the first to define the concept, we feel it necessary to point this out explicitly. [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, through an intuitive vanil la proximal method perspective, we derive a concise unified acceleration framework (UAF) for minimizing a convex function that has H\"older continuous derivatives with respect to general (non-Euclidean) norms. The UAF reconciles two different high-order acceleration approaches, one by Nesterov [Math. Program., 112 (2008), pp. 159-181] and one by Monteiro and Svaiter [SIAM J. Optim., 23 (2013), pp. 1092-1125]. As a result, the UAF unifies the high-order acceleration instances of the two approaches by only two problem-related parameters and two additional parameters for framework design. Meanwhile, the UAF (and its analysis) is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms. Furthermore, the UAF is the first approach that can match the existing lower bound of iteration complexity for minimizing a convex function with H\"older continuous derivatives. For practical implementation, we introduce a new and effective heuristic that significantly simplifies the binary search procedure required by the framework. We use experiments on logistic regression to verify the effectiveness of the heuristic. Finally, the UAF is proposed directly in the general composite convex setting and shows that the existing high-order algorithms can be naturally extended to the general composite convex setting. [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]

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]