Abstract: Abstract The study of non-convex penalties has recently received considerable attentions in sparse approximation. The existing non-convex penalties are proposed on the principle of seeking for a continuous alternative to the ℓ0-norm penalty. In this paper, we come up with a cubic spline penalty (CSP) which is also continuous but closer to ℓ0-norm penalty compared to the existing ones. As a result, it produces the weakest bias among them. Wavelet tight frames are efficient for sparse approximation due to its redundancy and fast implementation algorithm. We adopt a tight frame balanced model with our proposed cubic spline penalty since the balanced model takes the advantages of both analysis and synthesis model. To solve the non-convex CSP penalized problem, we employ a proximal local linear approximation (PLLA) algorithm and prove the generated sequence converges to a stationary point of the model if it is bounded. Under additional conditions, we find that the limit point behaves as well as the oracle solution, which is obtained by using the exact support of the ground truth signal. The efficiency of our cubic spline penalty are further demonstrated in applications of variable selection and image deblurring. PubDate: 2020-04-02

Abstract: Abstract Recently, the structured backward errors for the generalized saddle point problems with some different structures have been studied by some authors, but their results involve some Kronecker products, the vec-permutation matrices, and the orthogonal projection of a large block matrix which make them very expensive to compute when utilized for testing the stability of a practical algorithm or as an effective stopping criteria. In this paper, adopting a new technique, we present the explicit and computable formulae of the normwise structured backward errors for the generalized saddle point problems with five different structures. Our analysis can be viewed as a unified or general treatment for the structured backward errors for all kinds of saddle point problems and the derived results also can be seen as the generalizations of the existing ones for standard saddle point problems, including some Karush-Kuhn-Tucker systems. Some numerical experiments are performed to illustrate that our results can be easily used to test the stability of practical algorithms when applied some physical problems. We also show that the normwise structured and unstructured backward errors can be arbitrarily far apart in some certain cases. PubDate: 2020-04-02

Abstract: Abstract A second-order surface reconstruction (SR) method for the shallow water equations with a discontinuous bottom topography and a Manning friction source term is presented. We redefine the water surface level at the cell interface by using the minimum difference between the bottom level and the original water surface level. The reconstructed water surface level is used to define the intermediate bottom level and the intermediate water height at the cell interface. We propose an explicit-implicit method to address the friction source term. The new second-order SR scheme together with the explicit-implicit method can preserve a special steady-state solution of the system and can maintain the positivity of the water depth. We also extend the new scheme to two-dimensional shallow water flows. To demonstrate the robustness and effectiveness of the new scheme, we use several classical numerical experiments for the shallow water flows over a complex bottom topography. PubDate: 2020-04-02

Abstract: Abstract In general, it needs to take about nearly 10 grid points inside a wall boundary layer for low accuracy order methods to get satisfactory wall-normal gradient related results, such as friction coefficient and wall heat flux. If there exist extreme points inside the boundary layer, this situation becomes even worse. In this work, with the help of the analytic solution of the one-dimensional steady compressible Navier-Stokes equations under some restrictions, we show that the flow variables actually vary in the form of an exponential function instead of a polynomial one inside the boundary layer. Then, we propose an exponential space for approximating the solutions inside the boundary layer and numerically implementing it in the frame of direct discontinuous Galerkin (DDG) method. We show that the DDG methods based on the exponential boundary-layer space give much better numerical results for both conservative variables and wall-normal gradients than those with the standard polynomial space. Generally only 1–2 grid points inside the boundary layer are demanded to resolve the wall boundary layer to obtain satisfactory wall-normal gradients under the exponential space. Preliminary extension to two-dimensional laminar boundary-layer flow shows a similar performance of the proposed exponential boundary-layer space, exhibiting its potential applications in high dimensions. PubDate: 2020-03-30

Abstract: Abstract In this article, we propose a new method for low-rank completion of a large sparse matrix, subject to non-negativity constraint. As a challenging prototype of this problem, we have in mind the well-known Netflix problem. Our method is based on the derivation of a constrained gradient system and its numerical integration. The methods we propose are based on the constrained minimization of a functional associated to the low-rank completion matrix having minimal distance to the given matrix. In the main 2-level method, the low-rank matrix is expressed in the form of the non-negative factorization X = εUVT, where the factors U and V are assumed to be normalized with unit Frobenius norm. In the inner level—for a given ε—we minimize the functional; in the outer level, we tune the parameter ε until we reach a solution. Numerical experiments on well-known large test matrices show the effectiveness of the method when compared with other algorithms available in the literature. PubDate: 2020-03-23

Abstract: Abstract Quantifying the error that is induced by numerical approximation techniques is an important task in many fields of applied mathematics. Two characteristic properties of error bounds that are desirable are reliability and efficiency. In this article, we present an error estimation procedure for general nonlinear problems and, in particular, for parameter-dependent problems. With the presented auxiliary linear problem (ALP)-based error bounds and corresponding theoretical results, we can prove large improvements in the accuracy of the error predictions compared with existing error bounds. The application of the procedure in parametric model order reduction setting provides a particularly interesting setup, which is why we focus on the application in the reduced basis framework. Several numerical examples illustrate the performance and accuracy of the proposed method. PubDate: 2020-03-23

Abstract: Abstract Given the scalar sequence \(\{f_{m}\}^{\infty }_{m=0}\) that satisfies $$ f_{m} = \sum\limits_{i=1}^{k} {a_{i}}{\zeta}_{i}^{m},\quad m=0,1,\ldots, $$ where \(a_{i}, \zeta _{i}\in \mathbb {C}\) and ζi are distinct, the algorithm of Prony concerns the determination of the ai and the ζi from a finite number of the fm. This algorithm is also related to Padé approximants from the infinite power series \({\sum }^{\infty }_{j=0}f_{j}z^{j}\). In this work, we discuss ways of extending Prony’s algorithm to sequences of vectors \({\{\boldsymbol {f}_{m}\}}^{\infty }_{m=0}\) in \(\mathbb {C}^{N}\) that satisfy $$ \boldsymbol{f}_{m} = \sum\limits_{i=1}^{k} \boldsymbol{a}_{i} {\zeta}_{i}^{m}, \quad m=0,1,\ldots, $$ where \(\boldsymbol {a}_{i}\in \mathbb {C}^{N}\) and \(\zeta _{i}\in \mathbb {C}\). Two distinct problems arise depending on whether the vectors ai are linearly independent or not. We consider different approaches that enable us to determine the ai and ζi for these two problems, and develop suitable methods. We concentrate especially on extensions that take into account the possibility of the components of the ai being coupled. One of the applications we consider concerns the case in which $$ \boldsymbol{f}_{m} = \sum\limits_{i=1}^{r} \boldsymbol{a}_{i} {\zeta}_{i}^{m}, \quad m=0,1,\ldots,\quad r \text{ large}, $$ and we would like to approximate/determine of a number of the pairs (ζi, ai) for which ζi are largest. We present the related theory and provide numerical examples that confirm this theory. This application can be extended to the more general case in which $$ \boldsymbol{f}_{m} = \sum\limits_{i=1}^{r} \boldsymbol{p}_{i} (m){\zeta}_{i}^{m}, \quad m=0,1,\ldots, $$ where \(\boldsymbol {p}_{i}(m)\in \mathbb {C}^{N}\) are some (vector-valued) polynomials in m, and \(\zeta _{i}\in \mathbb {C}\) are distinct. Finally, the methods suggested here can be extended to vector sequences in infinite dimensional spaces in a straightforward manner. PubDate: 2020-03-19

Abstract: Abstract This paper considers Lévy noise driven nonlinear stochastic Volterra integral equations with doubly weakly singular kernels, whose singular points include both s = 0 and s = t. The existence and uniqueness theorem of the true solution as well as the strong convergence rate of the Euler–Maruyama (EM) method are developed via establishing some fine estimates. Compared with the corresponding results by Wang (Statist Probab Lett 78: 1062–1071, 2008) and Zhang (J Differential Equations 244: 2226–2250, 2008), our results generalize the Gaussian noise case to the Lévy noise case, relax the integrable limitations of singular kernels and establish an accurate convergence order. Moreover, based on the efficient sum-of-exponentials approximation, a fast EM method is presented to improve the low computational efficiency of the EM method. Specifically, when T ≫ 1, the computational complexity O(N2) and the storage O(N) of the EM method are reduced to \(O(N\log N)\) and \(O(\log N)\) respectively; while T ≈ 1, they are reduced to \(O(N\log ^{2} N)\) and \(O(\log ^{2} N)\) respectively, where T and N denote the terminal time and the total number of time steps respectively. Finally, the numerical example supports the theoretical results and explains the priority of the fast EM method. PubDate: 2020-03-18

Abstract: Abstract This paper deals with Pythagorean hodograph curves of the spaces of algebraic trigonometric functions and trigonometric polynomials, \(\text {span}\left \{1,t,\left \{{\cos \limits } \left ({kt}\right ), {\sin \limits } \left ({kt}\right )\right \}_{k=1}^{m}\right \} \) and \( \text {span}\left \{1,\left \{{\cos \limits } \left ({kt}\right ), {\sin \limits } \left ({kt}\right )\right \}_{k=1}^{m}\right \}, \) respectively. First, we propose a general characterization of planar PH curves in these spaces. Next, we consider the particular cases m = 1 and m = 2. For each of them, we give the general form of the control polygon of the PH curves, the implicit relations defining these curves, and their geometrical interpretations. Some examples and particular cases complete this study. PubDate: 2020-03-16

Abstract: Abstract The paper deals with numerical discretizations of separable nonlinear Hamiltonian systems with additive noise. For such problems, the expected value of the total energy, along the exact solution, drifts linearly with time. We present and analyze a time integrator having the same property for all times. Furthermore, strong and weak convergence of the numerical scheme along with efficient multilevel Monte Carlo estimators are studied. Finally, extensive numerical experiments illustrate the performance of the proposed numerical scheme. PubDate: 2020-03-16

Abstract: Abstract In this paper, we propose a discontinuous finite volume element method to solve a phase field model for two immiscible incompressible fluids. In this finite volume element scheme, discontinuous linear finite element basis functions are used to approximate the velocity, phase function, and chemical potential while piecewise constants are used to approximate the pressure. This numerical method is efficient, optimally convergent, conserving the mass, convenient to implement, flexible for mesh refinement, and easy to handle complex geometries with different types of boundary conditions. We rigorously prove the mass conservation property and the discrete energy dissipation for the proposed fully discrete discontinuous finite volume element scheme. Using numerical tests, we verify the accuracy, confirm the mass conservation and the energy law, test the influence of surface tension and small density variations, and simulate the driven cavity, the Rayleigh-Taylor instability. PubDate: 2020-03-14

Abstract: Abstract In this paper, a sine pseudo-spectral-difference scheme that preserves the discrete mass and energy is presented and analyzed for the coupled Gross–Pitaevskii equations with Dirichlet boundary conditions in several spatial dimensions. The Crank–Nicolson finite difference method is employed for approximating the time derivative, and the second-order sine spectral differentiation matrix is deduced and applied in spatial discretization. Without any restrictions on the grid ratios, optimal error estimates are established by utilizing the discrete energy method and the equivalence of (semi-)norms. An accelerated algorithm is developed to speed up the numerical implementation with the help of fast sine transform. Numerical examples are tested to confirm the effectiveness and high accuracy of the method. PubDate: 2020-03-14

Abstract: Abstract In this paper, we discuss a priori error estimates of two-grid mixed finite element methods for a class of nonlinear parabolic equations. The lowest order Raviart-Thomas mixed finite element and Crank-Nicolson scheme are used for the spatial and temporal discretization. First, we derive the optimal a priori error estimates for all variables. Second, we present a two-grid scheme and analyze its convergence. It is shown that if the two mesh sizes satisfy h = H2, then the two-grid method achieves the same convergence property as the Raviart-Thomas mixed finite element method. Finally, we give a numerical example to verify the theoretical results. PubDate: 2020-03-10

Abstract: Abstract In this paper, we propose a linearly implicit Fourier pseudo-spectral scheme, which preserves the total mass and energy conservation laws for the damped nonlinear Schrödinger equation in three dimensions. With the aid of the semi-norm equivalence between the Fourier pseudo-spectral method and the finite difference method, an optimal L2-error estimate for the proposed method without any restriction on the grid ratio is established by analyzing the real and imaginary parts of the error function. Numerical results are addressed to confirm our theoretical analysis. PubDate: 2020-03-09

Abstract: Abstract Let \(\mathbf d=(d_{j})_{j\in \mathbb {I}_{m}}\in \mathbb {N}^{m}\) be a finite sequence (of dimensions) and \(\alpha =(\alpha _{i})_{i\in \mathbb {I}_{n}}\) be a sequence of positive numbers (of weights), where \(\mathbb {I}_{k}=\{1,\ldots ,k\}\) for \(k\in \mathbb {N}\). We introduce the (α, d)-designs, i.e., m-tuples \({\Phi }=(\mathcal F_{j})_{j\in \mathbb {I}_{m}}\) such that \(\mathcal F_{j}=\{f_{ij}\}_{i\in \mathbb {I}_{n}}\) is a finite sequence in \(\mathbb {C}^{d_{j}}\), \(j\in \mathbb {I}_{m}\), and such that the sequence of non-negative numbers \((\ f_{ij}\ ^{2})_{j\in \mathbb {I}_{m}}\) forms a partition of αi, \(i\in \mathbb {I}_{n}\). We characterize the existence of (α, d)-designs with prescribed properties in terms of majorization relations. We show, by means of a finite step algorithm, that there exist (α, d)-designs \({\Phi }^{\text {op}}=(\mathcal {F}_{j}^{\text {op}})_{j\in \mathbb {I}_{m}}\) that are universally optimal; that is, for every convex function \(\varphi :[0,\infty )\rightarrow [0,\infty )\), then Φop minimizes the joint convex potential induced by φ among (α, d)-designs, namely $ \sum \limits_{j\in \mathbb I_{m}}\text {P}_{\varphi }(\mathcal F_{j}^{\text {op}})\leq \sum \limits_{j\in \mathbb I_{m}}\text {P}_{\varphi }(\mathcal F_{j}) $ for every (α, d)-design \({\Phi }=(\mathcal F_{j})_{j\in \mathbb {I}_{m}}\), where \(\text {P}_{\varphi }(\mathcal F)=\text {tr}(\varphi (S_{\mathcal {F}}))\); in particular, Φop minimizes both the joint frame potential and the joint mean square error among (α, d)-designs. We show that in this case, \(\mathcal {F}_{j}^{\text {op}}\) is a frame for \(\mathbb {C}^{d_{j}}\), for \(j\in \mathbb {I}_{m}\). This corresponds to the existence of optimal encoding-decoding schemes for multitasking devices with energy restrictions. PubDate: 2020-03-07

Abstract: Abstract We study worst-case optimal approximation of positive linear functionals in reproducing kernel Hilbert spaces induced by increasingly flat Gaussian kernels. This provides a new perspective and some generalisations to the problem of interpolation with increasingly flat radial basis functions. When the evaluation points are fixed and unisolvent, we show that the worst-case optimal method converges to a polynomial method. In an additional one-dimensional extension, we allow also the points to be selected optimally and show that in this case convergence is to the unique Gaussian quadrature–type method that achieves the maximal polynomial degree of exactness. The proofs are based on an explicit characterisation of the reproducing kernel Hilbert space of the Gaussian kernel in terms of exponentially damped polynomials. PubDate: 2020-03-06

Abstract: Abstract The eigenvalues and eigenfunctions of the Stokes operator have been the subject of intense analytical investigation and have applications in the study and simulation of the Navier–Stokes equations. As the Stokes operator is second order and has the divergence-free constraint, computing these eigenvalues and the corresponding eigenfunctions is a challenging task, particularly in complex geometries and at high frequencies. The boundary integral equation (BIE) framework provides robust and scalable eigenvalue computations due to (a) the reduction in the dimension of the problem to be discretized and (b) the absence of high-frequency “pollution” when using Green’s function to represent propagating waves. In this paper, we detail the theoretical justification for a BIE approach to the Stokes eigenvalue problem on simply- and multiply-connected planar domains, which entails a treatment of the uniqueness theory for oscillatory Stokes equations on exterior domains. Then, using well-established techniques for discretizing BIEs, we present numerical results which confirm the analytical claims of the paper and demonstrate the efficiency of the overall approach. PubDate: 2020-03-03

Abstract: Abstract We present the nonconforming virtual element method for the fourth-order singular perturbation problem. The virtual element proposed in this paper is a variant of the C0-continuous nonconforming virtual element presented in our previous work and allows to compute two different projection operators that are used for the construction of the discrete scheme. We show the optimal convergence in the energy norm for the nonconforming virtual element method. Further, the lowest order nonconforming method is proved to be uniformly convergent with respect to the perturbation parameter. Finally, we verify the convergence for the nonconforming virtual element method by some numerical tests. PubDate: 2020-02-27

Abstract: Abstract Two fundamental difficulties are encountered in the numerical evaluation of time-dependent layer potentials. One is the quadratic cost of history dependence, which has been successfully addressed by splitting the potentials into two parts—a local part that contains the most recent contributions and a history part that contains the contributions from all earlier times. The history part is smooth, easily discretized using high-order quadratures, and straightforward to compute using a variety of fast algorithms. The local part, however, involves complicated singularities in the underlying Green’s function. Existing methods, based on exchanging the order of integration in space and time, are able to achieve high-order accuracy, but are limited to the case of stationary boundaries. Here, we present a new quadrature method that leaves the order of integration unchanged, making use of a change of variables that converts the singular integrals with respect to time into smooth ones. We have also derived asymptotic formulas for the local part that lead to fast and accurate hybrid schemes, extending earlier work for scalar heat potentials and applicable to moving boundaries. The performance of the overall scheme is demonstrated via numerical examples. PubDate: 2020-02-27

Abstract: Abstract We introduce stochastic variants of the classical Bernstein polynomials associated with a continuous function f, built up from a general triangular array of random variables. We discuss the uniform convergence in probability of the approximation process that they represent, providing at the same time rates of convergence. In the particular case in which the triangular array of random variables consists of the uniform order statistics, we give a positive answer to a conjectured raised in Wu and Zhou (Adv. Comput. Math. 46, 8, 2020) about an exponential rate of convergence in probability. PubDate: 2020-02-27