Large ∣k∣ Behavior of Complex Geometric Optics Solutions to d-bar Problems

Complex geometric optics solutions to a system of d-bar equations appearing in the context of electrical impedance tomography and the scattering theory of the integrable Davey-Stewartson II equations are studied for large values of the spectral parameter k. For potentials $q\in {⟨\cdot ⟩}^{-2}{H}^s\left(ℂ\right)$ for some $s\in \left]1,2\right]$, it is shown that the solution converges as the geometric series in $1/{\left|k\right|}^{s-1}$. For potentials q being the characteristic function of a strictly convex open set with smooth boundary, this still holds with s = 3/2, i.e., with $1/\sqrt{\mid k\mid }$ instead of $1/{\left|k\right|}^{s-1}$. The leading-order contributions are computed explicitly. Numerical simulations show the applicability of the asymptotic formulae for the example of the characteristic function of the disk. © 2022 Courant Institute of Mathematics and Wiley Periodicals LLC.     

Online Prediction with History-Dependent Experts: The General Case

We study the problem of prediction of binary sequences with expert advice in the online setting, which is a classic example of online machine learning. We interpret the binary sequence as the price history of a stock, and view the predictor as an investor, which converts the problem into a stock prediction problem. In this framework, an investor, who predicts the daily movements of a stock, and an adversarial market, who controls the stock, play against each other over N turns. The investor combines the predictions of $n\ge 2$ experts in order to make a decision about how much to invest at each turn, and aims to minimize their regret with respect to the best-performing expert at the end of the game. We consider the problem with history-dependent experts, in which each expert uses the previous d days of history of the market in making their predictions. We prove that the value function for this game, rescaled appropriately, converges as $N\to \mathrm{\infty }$ at a rate of $O\left(N^{-1/6}\right)$ to the viscosity solution of a nonlinear degenerate elliptic PDE, which can be understood as the Hamilton-Jacobi-Issacs equation for the two-person game. As a result, we are able to deduce asymptotically optimal strategies for the investor. Our results extend those established by the first author and R.V. Kohn [14] for $n=2$ experts and $d\le 4$ days of history. © 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.     

Traveling Wave Solutions to the Free Boundary Incompressible Navier-Stokes Equations

In this paper we study a finite-depth layer of viscous incompressible fluid in dimension $n\ge 2$, modeled by the Navier-Stokes equations. The fluid is assumed to be bounded below by a flat rigid surface and above by a free, moving interface. A uniform gravitational field acts perpendicularly to the flat surface, and we consider the cases with and without surface tension acting on the free interface. In addition to these gravity-capillary effects, we allow for a second force field in the bulk and an external stress tensor on the free interface, both of which are posited to be in traveling wave form, i.e., time-independent when viewed in a coordinate system moving at a constant velocity parallel to the rigid lower boundary. We prove that, with surface tension in dimension $n\ge 2$ and without surface tension in dimension $n=2$, for every nontrivial traveling velocity there exists a nonempty open set of force and stress data that give rise to traveling wave solutions. While the existence of inviscid traveling waves is well-known, to the best of our knowledge this is the first construction of viscous traveling wave solutions. Our proof involves a number of novel analytic ingredients, including: the study of an overdetermined Stokes problem and its underdetermined adjoint problem, a delicate asymptotic development of the symbol for a normal-stress to normal-Dirichlet map defined via the Stokes operator, a new scale of specialized anisotropic Sobolev spaces, and the study of a pseudodifferential operator that synthesizes the various operators acting on the free surface functions. © 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.     

Backward error analysis of specified eigenpairs for sparse matrix polynomials

This article studies the unstructured and structured backward error analysis of specified eigenpairs for matrix polynomials. The structures we discuss include $T$-symmetric, $T$-skew-symmetric, Hermitian, skew Hermitian, $T$-even, $T$-odd, $H$-even, $H$-odd, $T$-palindromic, $T$-anti-palindromic, $H$-palindromic, and $H$-anti-palindromic matrix polynomials. Minimally structured perturbations are constructed with respect to Frobenius norm such that specified eigenpairs become exact eigenpairs of an appropriately perturbed matrix polynomial that also preserves sparsity. Further, we have used our results to solve various quadratic inverse eigenvalue problems that arise from real-life applications.     

Optimal standby activation in m-out-of-n systems: A preventive approach

This article investigates an optimal preventive standby activation policy for an $m$-out-of-$n$ redundant system. We assume that for such a system, which starts operating at time $t=0$, a standby component will be activated at either the failure time of the system or at a predetermined time $\tau$, whichever occurs first. We first obtain the system reliability function under this switching policy as a function of $\tau$. Then, we investigate the optimal switching time $\tau$ so that the mean time to failure of the system is maximized. The results indicate that the existence of an optimal value of $\tau$ depends on the lifetime of the standby redundancy and its virtual age in the standby state. Some illustrative examples are presented to examine the theoretical outcomes.     

Asymptotics for the eigenvalues of Toeplitz matrices with a symbol having a power singularity

The present work is devoted to the construction of an asymptotic expansion for the eigenvalues of a Toeplitz matrix $T_n(a)$ as $n$ goes to infinity, with a continuous and real-valued symbol $a$ having a power singularity of degree $\gamma$ with , at one point. The resulting matrix is dense and its entries decrease slowly to zero when moving away from the main diagonal, we apply the so called simple-loop (SL) method for constructing and justifying a uniform asymptotic expansion for all the eigenvalues. Note however, that the considered symbol does not fully satisfy the conditions imposed in previous works, but only in a small neighborhood of the singularity point. In the present work: (i) We construct and justify the asymptotic formulas of the SL method for the eigenvalues ${\lambda }_j(T_n(a))$ with $j⩾\epsilon n$, where the eigenvalues are arranged in nondecreasing order and $\epsilon$ is a sufficiently small fixed number. (ii) We show, with the help of numerical calculations, that the obtained formulas give good approximations in the case . (iii) We numerically show that the main term of the asymptotics for eigenvalues with , formally obtained from the formulas of the SL method, coincides with the main term of the asymptotics constructed and justified in the classical works of Widom and Parter.     

Lower and upper bounds of condition number for Vandermonde-wise matrices and method of fundamental solutions using pseudo radial-lines

Consider the method of fundamental solutions (MFS) for 2D Laplace's equation in a bounded simply connected domain $S$. In the standard MFS, the source nodes are located on a closed contour outside the domain boundary $\mathrm{\Gamma }(=\partial S)$, which is called pseudo-boundary. For circular, elliptic, and general closed pseudo-boundaries, analysis and computation have been studied extensively. New locations of source nodes are proposed along two pseudo radial-lines outside $\mathrm{\Gamma }$. Numerical results are very encouraging and promising. Since the success of the MFS mainly depends on stability, our efforts are focused on deriving the lower and upper bounds of condition number (Cond). The study finds stability properties of new Vandermonde-wise matrices on nodes $x_i\in [a,b]$ with . The Vandermonde-wise matrix is called in this article if it can be decomposed into the standard Vandermonde matrix. New lower and upper bounds of Cond are first derived for the standard Vandermonde matrix, and then for new algorithms of the MFS using two pseudo radial-lines. Both lower and upper bounds of Cond are intriguing in the stability study for the MFS. Numerical experiments are carried out to verify the stability analysis made. Since the fundamental solutions (as $\{\ln |\overline{{PQ}_i}|\}$) are the basis functions of the MFS, new Vandermonde-wise matrices are found. Since the nodes $x_i\in [a,b]$ with may come from approximations and interpolations by the Laurent polynomials with singular part, the conclusions in this article are important not only to the MFS but also to matrix analysis.     

Colourings of star systems

An $e$‐star is a complete bipartite graph $K_{1,e}$. An $e$‐star system of order $n>1,S_e\left(n\right)$, is a partition of the edges of the complete graph $K_n$ into $e$‐stars. An $e$‐star system is said to be $k$‐colourable if its vertex set can be partitioned into $k$ sets (called colour classes) such that no $e$‐star is monochromatic. The system $S_e\left(n\right)$ is $k$‐chromatic if $S_e\left(n\right)$ is $k$‐colourable but is not $\left(k?1\right)$‐colourable. If every $k$‐colouring of an $e$‐star system can be obtained from some $k$‐colouring $?$ by a permutation of the colours, we say that the system is uniquely $k$‐colourable. In this paper, we first show that for any integer $k?2$, there exists a $k$‐chromatic 3‐star system of order $n$ for all sufficiently large admissible $n$. Next, we generalize this result for $e$‐star systems for any $e?3$. We show that for all $k?2$ and $e?3$, there exists a $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$). Finally, we prove that for all $k?2$ and $e?3$, there exists a uniquely $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$).     

Recovering orthogonal tensors under arbitrarily strong,but locally correlated,noise

We consider the problem of recovering an orthogonally decomposable tensor with a subset of elements distorted by noise with arbitrarily large magnitude. We focus on the particular case where each mode in the decomposition is corrupted by noise vectors with components that are correlated locally, that is, with nearby components. We show that this deterministic tensor completion problem has the unusual property that it can be solved in polynomial time if the rank of the tensor is sufficiently large. This is the polar opposite of the low-rank assumptions of typical low-rank tensor and matrix completion settings. We show that our problem can be solved through a system of coupled Sylvester-like equations and show how to accelerate their solution by an alternating solver. This enables recovery even with a substantial number of missing entries, for instance for $n$-dimensional tensors of rank $n$ with up to $40\%$ missing entries.     

Birkhoff Normal Form and Long Time Existence for Periodic Gravity Water Waves

We consider the gravity water waves system with a periodic one-dimensional interface in infinite depth and give a rigorous proof of a conjecture of Dyachenko-Zakharov [16] concerning the approximate integrability of these equations. More precisely, we prove a rigorous reduction of the water waves equations to its integrable Birkhoff normal form up to order 4. As a consequence, we also obtain a long-time stability result: periodic perturbations of a flat interface that are initially of size ε remain regular and small up to times of order ${\epsilon }^{-3}$. This time scale is expected to be optimal. © 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.     

Efficient algorithms for computing rank-revealing factorizations on a GPU

Standard rank-revealing factorizations such as the singular value decomposition (SVD) and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This article presents two alternative algorithms for computing a rank-revealing factorization of the form $\mathsf{A}=\mathsf{U}\mathsf{T}{\mathsf{V}}^{\ast }$, where $\mathsf{U}$ and $\mathsf{V}$ are orthogonal and $\mathsf{T}$ is trapezoidal (or triangular if $\mathsf{A}$ is square). Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. Numerical experiments illustrate that these algorithms achieve significant acceleration over finely tuned GPU implementations of the SVD while providing low rank approximation errors close to that of the SVD.     

Nonparametric significance tests for imperfect repair

Given the failure history for $K\ge 2$ independent and identical repairable systems, a nonparametric procedure is presented to test the null hypothesis of minimal repair (MR) against the alternative of imperfect repair. The main idea is that, under non-harmful (harmful) repair, systems that failed later (earlier) are more reliable than those that have failed (later). This fact allows one, at any moment in time, to rank the systems from more to less reliable and, hence, to define a vector that counts how many times the system ranked $r$ failed. When all the systems are time-truncated at the same time $T$, it is shown that, under the null hypothesis of MR, the vector of counts follows a multinomial distribution with class probabilities $p_r=K^{-1}$ for $r=1,\dots ,K$. The test proceeds by computing a chi-bar squared test statistic similar to the one used to test one-sided alternatives in the multinomial setup, which allows us to compute $p$-values using either asymptotic theory or a straightforward Monte Carlo simulation using the null multinomial distribution. Extension to the case of different truncation times is also discussed. The procedure is applied to two real datasets regarding equipment used in the mining industry.     

Fast solution of three-dimensional elliptic equations with randomly generated jumping coefficients by using tensor-structured preconditioners

In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in ${ℝ}^d$, $d=2,3$. Both the two-dimensional (2D) and three-dimensional (3D) elliptic problems are considered for the jumping equation coefficients built as a checkerboard type configuration of bumps randomly distributed on a large $L\times L$, or $L\times L\times L$ lattice, respectively. The finite element method discretization procedure on a 3D $n\times n\times n$ uniform tensor grid is described in detail, and the Kronecker tensor product approach is proposed for fast generation of the stiffness matrix. We introduce tensor techniques for the construction of the low Kronecker rank spectrally equivalent preconditioner in a periodic setting to be used in the framework of the preconditioned conjugate gradient iteration. The discrete 3D periodic Laplacian pseudo-inverse is first diagonalized in the Fourier basis, and then the diagonal matrix is reshaped into a fully populated third-order tensor of size $n\times n\times n$. The latter is approximated by a low-rank canonical tensor by using the multigrid Tucker-to-canonical tensor transform. As an example, we apply the presented solver in numerical analysis of stochastic homogenization method where the 3D elliptic equation should be solved many hundred times, and where for every random sampling of the equation coefficient one has to construct the new stiffness matrix and the right-hand side. The computational characteristics of the presented solver in terms of a lattice parameter $L$ and the grid-size, $n^d$, in both 2D and 3D cases are illustrated in numerical tests. Our solver can be used in various applications where the elliptic problem should be solved for a number of different coefficients for example, in many-particle dynamics, protein docking problems or stochastic modeling.     

More about divisibility in βN

We continue the research of an extension $\stackrel{～}{\mid }$ of the divisibility relation to the Stone-?ech compactification $\beta \mathbb{N}$. First we prove that ultrafilters we call prime actually possess the algebraic property of primality. Several questions concerning the connection between divisibilities in $\beta \mathbb{N}$ and nonstandard extensions of $\mathbb{N}$ are answered, providing a few more equivalent conditions for divisibility in $\beta \mathbb{N}$. Results on uncountable chains in $(\beta \mathbb{N},\stackrel{～}{\mid })$ are proved and used in a construction of a well-ordered chain of maximal cardinality. Probably the most interesting result is the existence of a chain of type $(\mathbb{R},<)$ in $(\beta \mathbb{N},\stackrel{～}{\mid })$. Finally, we consider ultrafilters without divisors in $\mathbb{N}$ and among them find the greatest class.     

Constructing the field of values of decomposable and general matrices using the ZNN based path following method

This paper describes and develops a fast and accurate path following algorithm that computes the field of values boundary curve $\partial F(A)$ for every conceivable complex or real square matrix $A$. It relies on the matrix flow decomposition algorithm that finds a proper block-diagonal flow representation for the associated hermitean matrix flow ${ℱ}_A(t)=\cos (t)H+\sin (t)K$ under unitary similarity if that is possible. Here ${ℱ}_A(t)$ is the 1-parameter-varying linear combination of the real and skew part matrices $H=(A+A^{\ast })/2$ and $K=(A-A^{\ast })/(2i)$ of $A$. For indecomposable matrix flows, ${ℱ}_A(t)$ has just one block and the ZNN based field of values algorithm works with ${ℱ}_A(t)$ directly. For decomposing flows ${ℱ}_A(t)$, the algorithm decomposes the given matrix $A$ unitarily into block-diagonal form $U^{\ast }AU=\text{diag}(A_j)$ with $j>1$ diagonal blocks $A_j$ whose individual sizes add up to the size of $A$. It then computes the field of values boundaries separately for each diagonal block $A_j$ using the path following ZNN eigenvalue method. The convex hull of all sub-fields of values boundary points $\partial F(A_j)$ finally determines the field of values boundary curve correctly for decomposing matrices $A$. The algorithm removes standard restrictions for path following FoV methods that generally cannot deal with decomposing matrices $A$ due to possible eigencurve crossings of ${ℱ}_A(t)$. Tests and numerical comparisons are included. Our ZNN based method is coded for sequential and parallel computations and both versions run very accurately and fast when compared with Johnson's Francis QR eigenvalue and Bendixson rectangle based method and compute global eigenanalyses of ${ℱ}_A(t_k)$ for large discrete sets of angles $t_k\in [0,2\pi ]$ more slowly.