A sparse Laplacian in tensor product wavelet coordinates

We construct a wavelet basis on the unit interval with respect to which both the (infinite) mass and stiffness matrix corresponding to the one-dimensional Laplacian are (truly) sparse and boundedly invertible. As a consequence, the (infinite) stiffness matrix corresponding to the Laplacian on the n-dimensional unit box with respect to the n-fold tensor product wavelet basis is also sparse and boundedly invertible. This greatly simplifies the implementation and improves the quantitative properties of an adaptive wavelet scheme to solve the multi-dimensional Poisson equation. The results extend to any second order partial differential operator with constant coefficients that defines a boundedly invertible operator.     

A parallel iterative solver for positive-definite systems with hybrid MPI–OpenMP parallelization for multi-core clusters

This article is devoted to the development and study of an algorithm for solving large systems of linear algebraic equations with sparse stiffness matrix on supercomputer by using the preconditioned conjugate gradient method (PCG). An efficient preconditioner is constructed on the basis of the domain decomposition method (the additive Schwarz method) which makes it possible to implement the algorithm on several computing nodes. We describe the parallel algorithm of the action of the stiffness matrix and the preconditioner on a vector. In addition, to increase the computational efficiency we make use of the routines from Intel^®MKL: the direct solver (PARDISO) and the matrix–vector multiplication for sparse matrices (Sparse BLAS). We also study efficiency of using OpenMP directives on each computational node and compare it with pure MPI parallelization. The corresponding performance and scalability charts are presented.     

Wavelet Collocation Methods for a First Kind Boundary Integral Equation in Acoustic Scattering

In this paper we consider a wavelet algorithm for the piecewise constant collocation method applied to the boundary element solution of a first kind integral equation arising in acoustic scattering. The conventional stiffness matrix is transformed into the corresponding matrix with respect to wavelet bases, and it is approximated by a compressed matrix. Finally, the stiffness matrix is multiplied by diagonal preconditioners such that the resulting matrix of the system of linear equations is well conditioned and sparse. Using this matrix, the boundary integral equation can be solved effectively.     

Fast simplicial finite element algorithms using Bernstein polynomials

Fast algorithms for applying finite element mass and stiffness operators to the B-form of polynomials over d-dimensional simplices are derived. These rely on special properties of the Bernstein basis and lead to stiffness matrix algorithms with the same asymptotic complexity as tensor-product techniques in rectangular domains. First, special structure leading to fast application of mass matrices is developed. Then, by factoring stiffness matrices into products of sparse derivative matrices with mass matrices, fast algorithms are also obtained for stiffness matrices.     

Approximate multiplication in adaptive wavelet methods

Cohen, Dahmen and DeVore designed in [Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 2001, 70(233), 27–75] and [Adaptive wavelet methods II¶beyond the elliptic case, Found. Comput. Math., 2002, 2(3), 203–245] a general concept for solving operator equations. Its essential steps are: transformation of the variational formulation into the well-conditioned infinite-dimensional l ₂-problem, finding the convergent iteration process for the l ₂-problem and finally using its finite dimensional approximation which works with an inexact right-hand side and approximate matrix-vector multiplication. In our contribution, we pay attention to approximate matrix-vector multiplication which is enabled by an off-diagonal decay of entries of the wavelet stiffness matrices. We propose a more efficient technique which better utilizes actual decay of matrix and vector entries and we also prove that this multiplication algorithm is asymptotically optimal in the sense that storage and number of floating point operations, needed to resolve the problem with desired accuracy, remain proportional to the problem size when the resolution of the discretization is refined.     

Stable three-point wavelet bases on general meshes

Summary. Recently, we introduced a wavelet basis on general, possibly locally refined linear finite element spaces. Each wavelet is a linear combination of three nodal basis functions, independently of the number of space dimensions. In the present paper, we show -stability of this basis for a range of , that in any case includes , which means that the corresponding additive Schwarz preconditioner is optimal for second order problems. Furthermore, we generalize the construction of the wavelet basis to manifolds. We show that the wavelets have at least one-, and in areas where the manifold is smooth and the mesh is uniform even two vanishing moments. Because of these vanishing moments, apart from preconditioning, the basis can be used for compression purposes: For a class of integral equation problems, the stiffness matrix with respect to the wavelet basis will be close to a sparse one, in the sense that, a priori, it can be compressed to a sparse matrix without the order of convergence being reduced. Received November 6, 1996 / Revised version received June 30, 1997     

A well-conditioned estimator for large-dimensional covariance matrices

Many applied problems require a covariance matrix estimator that is not only invertible, but also well-conditioned (that is, inverting it does not amplify estimation error). For large-dimensional covariance matrices, the usual estimator—the sample covariance matrix—is typically not well-conditioned and may not even be invertible. This paper introduces an estimator that is both well-conditioned and more accurate than the sample covariance matrix asymptotically. This estimator is distribution-free and has a simple explicit formula that is easy to compute and interpret. It is the asymptotically optimal convex linear combination of the sample covariance matrix with the identity matrix. Optimality is meant with respect to a quadratic loss function, asymptotically as the number of observations and the number of variables go to infinity together. Extensive Monte Carlo confirm that the asymptotic results tend to hold well in finite sample.     

Correction of stiffness and mass matrices utilizing simulated measured modal data

Measured and analytical data are unlikely to be equal due to measured noise, model inadequacies and structural damage, etc. It is necessary to update the physical parameters of analytical models for proper simulation and design studies. Starting from simulated measured modal data such as natural frequencies and their corresponding mode shapes, this study presents the equations to update the physical parameters of stiffness and mass matrices simultaneously for analytical modelling by minimizing a cost function in the satisfaction of the dynamic constraints of orthogonality requirement and eigenvalue function. The proposed equations are straightforwardly derived by Moore–Penrose inverse matrix without using any multipliers. The cost function is expressed by the sum of the quadratic forms of both the difference between analytical and updated mass, and stiffness matrices. The results are compared with the updated mass matrix to consider the orthogonality requirement only and the updated stiffness matrix to consider the eigenvalue function only, respectively. Also, they are compared with Wei’s method which updates the mass and stiffness matrices simultaneously. The validity of the proposed method is illustrated in an application to correct the mass and stiffness matrices due to section loss of some members in a simple truss structure.     

Numerical solution of hypersingular equation using recursive wavelet on invariant set

In this paper, we construct the Chebyshev recursive wavelets on a unit interval of the first kind, the second kind and their corresponding weight functions. We apply wavelet collocation method to solve the natural boundary integral equation of the harmonic equation on the lower half-plane numerically. It is convenient and accurate to generate the stiffness matrix. Two numerical examples are presented. It is shown that the stiffness matrix is highly sparse when the order of the stiffness matrix becomes large. Current method allows choosing an appropriate weight function to increase the convergence rate and accuracy of the numerical results.     

Circulant Wavelet Preconditioners for Solving Elliptic Differential Equations and Boundary Integral Equations

In this paper is discussed solving an elliptic equation and a boundary integral equation of the second kind by representation of compactly supported wavelets. By using wavelet bases and the Galerkin method for these equations, we obtain a stiff sparse matrix that can be ill-conditioned. Therefore, we have to introduce an operator which maps every sparse matrix to a circulant sparse matrix. This class of circulant matrices is a class of preconditioners in a Banach space. Based on having some properties in the spectral theory for this class of matrices, we conclude that the circulant matrices are a good class of preconditioners for solving these equations. We called them circulant wavelet preconditioners (CWP). Therefore, a class of algorithms is introduced for rapid numerical application.     

瞬态动力问题的遂单元矩阵分裂和逐步积分方法

本文对瞬态动力问题,结合逐步积分方法提出了一类广义的矩阵分裂和逐单元松弛算法,摆脱了有限元法通常需形成总体刚度矩阵,总体质量矩阵和求解大型稀疏方程组的工作,理论分析和计算实例表明,本文的广义矩阵分裂是最优的分裂方案.本文的算法物理意义明确,便于编写程序推广应用.     

The resultant approach to computing vector characteristics of multiparameter polynomial matrices

Known types of resultant matrices corresponding to one-parameter matrix polynomials are generalized to the multiparameter case. Based on the resultant approach suggested, methods for solving the following problems for multiparameter polynomial matrices are developed: computing a basis of the matrix range, computing a minimal basis of the right null-space, and constructing the Jordan chains and semilattices of vectors associated with a multiple spectrum point. In solving these problems, the original polynomial matrix is not transformed. Methods for solving other parametric problems of algebra can be developed on the basis of the method for computing a minimal basis of the null-space of a polynomial matrix. Issues concerning the optimality of computing the null-spaces of sparse resultant matrices and numerical precision are not considered. Bibliography: 19 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 182–214.     

Hierarchical Riesz Bases for Hs(Ω), 1 < s < 5/2

On arbitrary polygonal domains $\Omega \subset \RR^2$, we construct $C^1$ hierarchical Riesz bases for Sobolev spaces $H^s(\Omega)$. In contrast to an earlier construction by Dahmen, Oswald, and Shi (1994), our bases will be of Lagrange instead of Hermite type, by which we extend the range of stability from $s \in (2,\frac{5}{2})$ to $s \in (1,\frac{5}{2})$. Since the latter range includes $s=2$, with respect to the present basis, the stiffness matrices of fourth-order elliptic problems are uniformly well-conditioned.     

Wavelet-Galerkin methods: An adapted biorthogonal wavelet basis

In this paper we construct a compactly supported biorthogonal wavelet basis adapted to some simple differential operators. Moreover, we estimate the condition numbers of the corresponding stiffness matrices.     

Directional Haar wavelet frames on triangles

Traditional wavelets are not very effective in dealing with images that contain orientated discontinuities (edges). To achieve a more efficient representation one has to use basis elements with much higher directional sensitivity. In recent years several approaches like curvelets and shearlets have been studied providing essentially optimal approximation properties for images that are piecewise smooth and have discontinuities along C²-curves. While curvelets and shearlets have compact support in frequency domain, we construct directional wavelet frames generated by functions with compact support in time domain. Our Haar wavelet constructions can be seen as special composite dilation wavelets, being based on a generalized multiresolution analysis (MRA) associated with a dilation matrix and a finite collection of ‘shear’ matrices. The complete system of constructed wavelet functions forms a Parseval frame. Based on this MRA structure we provide an efficient filter bank algorithm. The freedom obtained by the redundancy of the applied Haar functions will be used for an efficient sparse representation of piecewise constant images as well as for image denoising.     

On the choice of a multiplication algorithm for polynomials and polynomial matrices

We investigate multiplication algorithms for dense and sparse polynomials and polynomial matrices over different numerical domains and obtain expressions for the complexity of multiplication of polynomials and polynomial matrices understood as the expectation of the number of arithmetic operations. These expressions for a set of parameters of practical interest are tabulated. The results of experiments with the corresponding programs are presented. Bibliography: 8 titles.     

A nested dissection approach for sparse matrix partitioning

We consider how to partition and distribute sparse matrices among processors to reduce communication cost in sparse matrix computations, in particular, sparse matrix-vector multiplication. We consider 2d distributions, where the distribution is not constrained to just rows or columns. We present a new model and an algorithm based on vertex separators and nested dissection. Preliminary numerical results for sparse matrices from real applications indicate the new method performs consistently better than traditional 1d partitioning and is often also better than current 2d methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

CMV matrices with asymptotically constant coefficients. Szegö-Blaschke class, scattering theory

We develop a modern extended scattering theory for CMV matrices with asymptotically constant Verblunsky coefficients. We show that the traditional (Faddeev-Marchenko) condition is too restrictive to define the class of CMV matrices for which there exists a unique scattering representation. The main results are: (1) the class of twosided CMV matrices acting in l², whose spectral density satisfies the Szegö condition and whose point spectrum the Blaschke condition, corresponds precisely to the class where the scattering problem can be posed and solved. That is, to a given CMV matrix of this class, one can associate the scattering data and the FM space. The CMV matrix corresponds to the multiplication operator in this space, and the orthonormal basis in it (corresponding to the standard basis in l²) behaves asymptotically as the basis associated with the free system. (2) From the point of view of the scattering problem, the most natural class of CMV matrices is that one in which (a) the scattering data determine the matrix uniquely and (b) the associated Gelfand-Levitan-Marchenko transformation operators are bounded. Necessary and sufficient conditions for this class can be given in terms of an A₂ kind condition for the density of the absolutely continuous spectrum and a Carleson kind condition for the discrete spectrum. Similar conditions close to the optimal ones are given directly in terms of the scattering data.     

Overlapping Domain Decomposition Algorithms for General Sparse Matrices

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver.