Krenn, Gu and Zeilinger initiated the study of PMValid edge-colourings because of its connection to a problem from quantum physics. A graph is defined to have a PMValid $k$-edge-colouring if it admits a $k$-edge-colouring (i.e. an edge colouring with $k$-colours) with the property that all perfect matchings are monochromatic and each of the $k$ colour classes contain at least one perfect matching. The matching index of a graph $G$, $\mu(G)$ is defined as the maximum value of $k$ for which $G$ admits a PMValid $k$-edge-colouring. It is easy to see that $\mu(G)\geq 1$ if and only if $G$ has a perfect matching (due to the trivial $1$-edge-colouring which is PMValid). Bogdanov observed that for all graphs non-isomorphic to $K_4$, $\mu(G)\leq 2$ and $\mu(K_4)=3$. However, the characterisation of graphs for which $\mu(G)=1$ and $\mu(G)=2$ is not known. In this work, we answer this question. Using this characterisation, we also give a fast algorithm to compute $\mu(G)$ of a graph $G$. In view of our work, the structure of PMValid $k$-edge-colourable graphs is now fully understood for all $k$. Our characterisation, also has an implication to the aforementioned quantum physics problem. In particular, it settles a conjecture of Krenn and Gu for a sub-class of graphs.
We provide an algorithm for computing an effective basis of homology of elliptic surfaces over the complex projective line on which integration of periods can be carried out. This allows the heuristic recovery of several algebraic invariants of the surface, notably the N\'eron-Severi lattice, the transcendental lattice, the Mordell-Weil group and the Mordell-Weil lattice. This algorithm comes with a SageMath implementation.
We propose a method to numerically compute fractional derivatives (or the fractional Laplacian) on the whole real line via Riesz fractional integrals. The compactified real line is divided into a number of intervals, thus amounting to a multi-domain approach; after transformations in accordance with the underlying $Z_{q}$ curve ensuring analyticity of the respective integrands, the integrals over the different domains are computed with a Clenshaw-Curtis algorithm. As an example, we consider solitary waves for fractional Korteweg-de Vries equations and compare these to results obtained with a discrete Fourier transform.
The present work provides a comprehensive study of symmetric-conjugate operator splitting methods in the context of linear parabolic problems and demonstrates their additional benefits compared to symmetric splitting methods. Relevant applications include nonreversible systems and ground state computations for linear Schr\"odinger equations based on the imaginary time propagation. Numerical examples confirm the favourable error behaviour of higher-order symmetric-conjugate splitting methods and illustrate the usefulness of a time stepsize control, where the local error estimation relies on the computation of the imaginary parts and thus requires negligible costs.
The theory of generalized locally Toeplitz (GLT) sequences is a powerful apparatus for computing the asymptotic spectral distribution of matrices $A_n$ arising from numerical discretizations of differential equations. Indeed, when the mesh fineness parameter $n$ tends to infinity, these matrices $A_n$ give rise to a sequence $\{A_n\}_n$, which often turns out to be a GLT sequence. In this paper, we extend the theory of GLT sequences in several directions: we show that every GLT sequence enjoys a normal form, we identify the spectral symbol of every GLT sequence formed by normal matrices, and we prove that, for every GLT sequence $\{A_n\}_n$ formed by normal matrices and every continuous function $f:\mathbb C\to\mathbb C$, the sequence $\{f(A_n)\}_n$ is again a GLT sequence whose spectral symbol is $f(\kappa)$, where $\kappa$ is the spectral symbol of $\{A_n\}_n$. In addition, using the theory of GLT sequences, we prove a spectral distribution result for perturbed normal matrices.
It is known that standard stochastic Galerkin methods encounter challenges when solving partial differential equations with high-dimensional random inputs, which are typically caused by the large number of stochastic basis functions required. It becomes crucial to properly choose effective basis functions, such that the dimension of the stochastic approximation space can be reduced. In this work, we focus on the stochastic Galerkin approximation associated with generalized polynomial chaos (gPC), and explore the gPC expansion based on the analysis of variance (ANOVA) decomposition. A concise form of the gPC expansion is presented for each component function of the ANOVA expansion, and an adaptive ANOVA procedure is proposed to construct the overall stochastic Galerkin system. Numerical results demonstrate the efficiency of our proposed adaptive ANOVA stochastic Galerkin method for both diffusion and Helmholtz problems.
We consider the surface Stokes equation on a smooth closed hypersurface in three-dimensional space. For discretization of this problem a generalization of the surface finite element method (SFEM) of Dziuk-Elliott combined with a Hood-Taylor pair of finite element spaces has been used in the literature. We call this method Hood-Taylor-SFEM. This method uses a penalty technique to weakly satisfy the tangentiality constraint. In this paper we present a discretization error analysis of this method resulting in optimal discretization error bounds in an energy norm. We also address linear algebra aspects related to (pre)conditioning of the system matrix.
We establish optimal error bounds on time-splitting methods for the nonlinear Schr\"odinger equation with low regularity potential and typical power-type nonlinearity $ f(\rho) = \rho^\sigma $, where $ \rho:=|\psi|^2 $ is the density with $ \psi $ the wave function and $ \sigma > 0 $ the exponent of the nonlinearity. For the first-order Lie-Trotter time-splitting method, optimal $ L^2 $-norm error bound is proved for $L^\infty$-potential and $ \sigma > 0 $, and optimal $H^1$-norm error bound is obtained for $ W^{1, 4} $-potential and $ \sigma \geq 1/2 $. For the second-order Strang time-splitting method, optimal $ L^2 $-norm error bound is established for $H^2$-potential and $ \sigma \geq 1 $, and optimal $H^1$-norm error bound is proved for $H^3$-potential and $ \sigma \geq 3/2 $ (or $\sigma = 1$). Compared to those error estimates of time-splitting methods in the literature, our optimal error bounds either improve the convergence rates under the same regularity assumptions or significantly relax the regularity requirements on potential and nonlinearity for optimal convergence orders. A key ingredient in our proof is to adopt a new technique called \textit{regularity compensation oscillation} (RCO), where low frequency modes are analyzed by phase cancellation, and high frequency modes are estimated by regularity of the solution. Extensive numerical results are reported to confirm our error estimates and to demonstrate that they are sharp.
In general, providing an axiomatization for an arbitrary logic is a task that may require some ingenuity. In the case of logics defined by a finite logical matrix (three-valued logics being a particularly simple example), the generation of suitable finite axiomatizations can be completely automatized, essentially by expressing the matrix tables via inference rules. In this chapter we illustrate how two formalisms, the 3-labelled calculi of Baaz, Ferm\"uller and Zach and the multiple-conclusion (or Set-Set) Hilbert-style calculi of Shoesmith and Smiley, may be uniformly employed to axiomatize logics defined by a three-valued logical matrix. The generating procedure common to both formalisms can be described as follows: first (i) convert the matrix semantics into rule form (we refer to this step as the generating subprocedure) and then (ii) simplify the set of rules thus obtained, essentially relying on the defining properties of any Tarskian consequence relation (we refer to this step as the streamlining subprocedure). We illustrate through some examples that, if a minimal expressiveness assumption is met (namely, if the matrix defining the logic is monadic), then it is straightforward to define effective translations guaranteeing the equivalence between the 3-labelled and the Set-Set approach.
This work deals with an inverse source problem for the biharmonic wave equation. A two-stage numerical method is proposed to identify the unknown source from the multi-frequency phaseless data. In the first stage, we introduce some artificially auxiliary point sources to the inverse source system and establish a phase retrieval formula. Theoretically, we point out that the phase can be uniquely determined and estimate the stability of this phase retrieval approach. Once the phase information is retrieved, the Fourier method is adopted to reconstruct the source function from the phased multi-frequency data. The proposed method is easy-to-implement and there is no forward solver involved in the reconstruction. Numerical experiments are conducted to verify the performance of the proposed method.
We study least-squares trace regression when the parameter is the sum of a $r$-low-rank matrix and a $s$-sparse matrix and a fraction $\epsilon$ of the labels is corrupted. For subgaussian distributions and feature-dependent noise, we highlight three needed design properties, each one derived from a different process inequality: a "product process inequality", "Chevet's inequality" and a "multiplier process inequality". These properties handle, simultaneously, additive decomposition, label contamination and design-noise interaction. They imply the near-optimality of a tractable estimator with respect to the effective dimensions $d_{eff,r}$ and $d_{eff,s}$ of the low-rank and sparse components, $\epsilon$ and the failure probability $\delta$. The near-optimal rate is $\mathsf{r}(n,d_{eff,r}) + \mathsf{r}(n,d_{eff,s}) + \sqrt{(1+\log(1/\delta))/n} + \epsilon\log(1/\epsilon)$, where $\mathsf{r}(n,d_{eff,r})+\mathsf{r}(n,d_{eff,s})$ is the optimal rate in average with no contamination. Our estimator is adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$, it attains the mentioned rate with probability $1-\delta$ uniformly over all $\delta\ge\exp(-cn)$. Without matrix decomposition, our analysis also entails optimal bounds for a robust estimator adapted to the noise variance. Our estimators are based on "sorted" versions of Huber's loss. We present simulations matching the theory. In particular, it reveals the superiority of "sorted" Huber's losses over the classical Huber's loss.