Multilevel algorithms for finite difference discretizations on sparse grids

We propose some algorithms to solve the system of linear equations arising from the finite difference discretization on sparse grids. For this, we will use the multilevel structure of the sparse grid space or its full grid subspaces, respectively.     

A CLASS OF FACTORIZATION UPDATE ALGORITHM FOR SOLVING SYSTEMS OF SPARSE NONLINEAR EQUATIONS

ＡＣＬＡＳＳＯＦＦＡＣＴＯＲＩＺＡＴＩＯＮＵＰＤＡＴＥＡＬＧＯＲＩＴＨＭＦＯＲＳＯＬＶＩＮＧＳＹＳＴＥＭＳＯＦＳＰＡＲＳＥＮＯＮＬＩＮＥＡＲＥＱＵＡＴＩＯＮＳＢＡＩＺＨＯＮＧＺＨＩ（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔａｔｉｏｎａｌＭａｔｈｅｍａｔｉｃ...     

A discrete dynamics approach to sparse calculation and applied in ontology science

ABSTRACT

In the era of big data, with the increase of data processing information and the increase of data complexity, higher requirements are put on the tools and algorithms of data processing. As a tool for structured information representation, ontology has been used in engineering fields such as chemistry, biology, pharmacy, and materials. As a dynamic structure, the increasing concepts contributes to a gradual increase of a single ontology. In order to solve the problem of computational complexity decreasing in the procedure of similarity calculating, the techniques of dimensionality reduction and sparse computing are applied to ontology learning. This article presents discrete dynamics approach showing several tricks on applying the sparse computing method to ontology learning, and verify its efficiency through experiments.     

Spatially adaptive sparse grids for high-dimensional data-driven problems

Sparse grids allow one to employ grid-based discretization methods in data-driven problems. We present an extension of the classical sparse grid approach that allows us to tackle high-dimensional problems by spatially adaptive refinement, modified ansatz functions, and efficient regularization techniques. The competitiveness of this method is shown for typical benchmark problems with up to 166 dimensions for classification in data mining, pointing out properties of sparse grids in this context. To gain insight into the adaptive refinement and to examine the scope for further improvements, the approximation of non-smooth indicator functions with adaptive sparse grids has been studied as a model problem. As an example for an improved adaptive grid refinement, we present results for an edge-detection strategy.     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

GLOBAL CONVERGENCE OF QPFTH METHOD FOR LARGE-SCALE NONLINEAR SPARSE CONSTRAINED OPTIMIZATION

1.IntroductionIn[6],aQPFTHmethodwasproposedforsolvingthefollowingnonlinearprogrammingproblemwherefunctionsf:R"-- RIandgi:R"-- R',jeJaretwicecontinuouslydifferentiable.TheQPFTHalgorithmwasdevelopedforsolvingsparselarge-scaleproblem(l.l)andwastwo-stepQ-quadraticallyandR-quadraticallyconvergent(see[6]).Theglobalconvergenceofthisalgorithmisdiscussedindetailinthispaper.Forthefollowinginvestigationwerequiresomenotationsandassumptions.TheLagrangianofproblem(1.1)isdefinedbyFOundationofJiangs…     

Periodic interpolation and wavelets on sparse grids

Nested spaces of multivariate periodic functions forming a non-stationary multiresolution analysis are investigated. The scaling functions of these spaces are fundamental polynomials of Lagrange interpolation on a sparse grid. The approach based on Boolean sums leads to sample and wavelet spaces of significantly lower dimension and good approximation order. The algorithms for complete decomposition and reconstruction are of simple structure and low complexity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Mixed methods with dynamic finite-element spaces for miscible displacement in porous media

Miscible displacement in porous media is modeled by a nonlinear coupled system of two partial differential equations. We approximate the pressure equation, which is elliptic, and the concentration equation, which is parabolic but normally convection-dominated, by the mixed methods with dynamic finite-element spaces, i.e., different number of elements and different basis functions are adopted at different time levels; and the approximate concentration is projected onto the next finite-element space in weighted L²-norm for starting a new time step. This allows us to make local grid refinements or unrefinements and basis function improvements. Two fully discrete schemes are presented and analysed. Error estimates show that these methods have optimal convergent rate in some sense. The efficiency and capability of the dynamic finite-element method are commented for accurately solving time-dependent problems with localized phenomena, such as fronts, shocks, and boundary layers.     

Inexact trust region method for large sparse systems of nonlinear equations

The main purpose of this paper is to prove the global convergence of the new trust region method based on the smoothed CGS algorithm. This method is surprisingly convenient for the numerical solution of large sparse systems of nonlinear equations, as is demonstrated by numerical experiments. A modification of the proposed trust region method does not use matrices, so it can be used for large dense systems of nonlinear equations.     

Option pricing with a direct adaptive sparse grid approach

We present an adaptive sparse grid algorithm for the solution of the Black–Scholes equation for option pricing, using the finite element method. Sparse grids enable us to deal with higher-dimensional problems better than full grids. In contrast to common approaches that are based on the combination technique, which combines different solutions on anisotropic coarse full grids, the direct sparse grid approach allows for local adaptive refinement. When dealing with non-smooth payoff functions, this reduces the computational effort significantly. In this paper, we introduce the spatially adaptive discretization of the Black–Scholes equation with sparse grids and describe the algorithmic structure of the numerical solver. We present several strategies for adaptive refinement, evaluate them for different dimensionalities, and demonstrate their performance showing numerical results.     

A multilevel approach for nonnegative matrix factorization

Nonnegative matrix factorization (NMF), the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices, has been shown to be useful in many applications, such as text mining, image processing, and computational biology. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their initial convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. Several simple multilevel strategies are described and are experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

Parallel sparse linear algebra and application to structural mechanics

The framework of this paper is the parallelization of a plasticity algorithm that uses an implicit method and an incremental approach. More precisely, we will focus on some specific parallel sparse linear algebra algorithms which are the most time-consuming steps to solve efficiently such an engineering application. First, we present a general algorithm which computes an efficient static scheduling of block computations for parallel sparse linear factorization. The associated solver, based on a supernodal fan-in approach, is fully driven by this scheduling. Second, we describe a scalable parallel assembly algorithm based on a distribution of elements induced by the previous distribution for the blocks of the sparse matrix. We give an overview of these algorithms and present performance results on an IBM SP2 for a collection of grid and irregular problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hybrid methods for large sparse nonlinear least squares

Hybrid methods are developed for improving the Gauss-Newton method in the case of large residual or ill-conditioned nonlinear least-square problems. These methods are used usually in a form suitable for dense problems. But some standard approaches are unsuitable, and some new possibilities appear in the sparse case. We propose efficient hybrid methods for various representations of the sparse problems. After describing the basic ideas that help deriving new hybrid methods, we are concerned with designing hybrid methods for sparse Jacobian and sparse Hessian representations of the least-square problems. The efficiency of hybrid methods is demonstrated by extensive numerical experiments.This work was supported by the Czech Republic Grant Agency, Grant 201/93/0129. The author is indebted to Jan Vlek for his comments on the first draft of this paper and to anonymous referees for many useful remarks.     

Mortar method for matching grids in a mixed scheme as applied to the biharmonic equation

Nitsche’s mortar method for matching grids in the Hermann-Miyoshi mixed scheme for the biharmonic equation is considered. A two-parameter mortar problem is constructed and analyzed. Existence and uniqueness theorems are proved under certain constraints on the parameters. The norm of the difference between the solutions to the mortar and original problems is estimated. The convergence rates are the same as in the Hermann-Miyoshi scheme on matching grids.     

Statistical gap Tauberian theorems in metric spaces

By using the concept of statistical convergence we present statistical Tauberian theorems of gap type for the Cesàro, Euler-Borel family and the Hausdorff families applicable in arbitrary metric spaces. In contrast to the classical gap Tauberian theorems, we show that such theorems exist in the statistical sense for the convolution methods which include the Taylor and the Borel matrix methods. We further provide statistical analogs of the gap Tauberian theorems for the Hausdorff methods and provide an explanation as to how the Tauberian rates over the gaps may differ from those of the classical Tauberian theorems.     

On the updating scheme in a class of collinear scaling algorithms for sparse minimization

Sorensen (Ref. 1) has proposed a class of algorithms for sparse unconstrained minimization where the sparsity pattern of the Cholesky factors of the Hessian is known. His updates at each iteration depend on the choice of a vector, and in Ref. 1 the question of choosing this vector is essentially left open. In this note, we propose a variational problem whose solution may be used to choose this vector. The major part of the computation of a solution to this variational problem is similar to the computation of a trust-region step in unconstrained minimization. Therefore, well-developed techniques available for the latter problem can be used to compute this vector and to perform the updating.This research was supported by NSF Grant DMS-8414460 and by DOE Grant DE-FG06-85ER25007, awarded to Washington State University, and by the Applied Mathematical Sciences Subprogram of the US Department of Energy under Contract W-31-109-Eng-38 while the first author was visiting the Mathematics and Computer Science Division of Argonne National Laboratory.     

A new approach to fixed point theorems on G-metric spaces

In this paper, we introduce the metric d^G$d^G$ on a G  -metric space (X,G)$(X,G)$ and use this notion to show that many contraction conditions for maps on the G  -metric space (X,G)$(X,G)$ reduce to certain contraction conditions for maps on the metric space (X,d^G)$(X,d^G)$. As applications, the proofs of many fixed point theorems for maps on the G  -metric space (X,G)$(X,G)$ may be simplified, and many fixed point theorems for maps on the G  -metric space (X,G)$(X,G)$ are direct consequences of preceding results for maps on the metric space (X,d^G)$(X,d^G)$.