A sparse grid method for the Navier–Stokes equations based on hyperbolic cross

A sparse grid method for the time‐dependent Navier–Stokes equations based on hyperbolic cross approximation is considered in this article. Subsequent truncation of the associated series expansion results in a sparse grid discretization. Stability and convergence of the fully discrete sparse grid method are established. Finally, the numerical experiment is presented to show the effectiveness of this sparse grid method. Copyright © 2013 John Wiley & Sons, Ltd.     

自适应稀疏伪谱逼近新方法

自适应稀疏伪谱逼近法是广义混沌多项式类方法的最新进展,相对于其它方法具有计算精度高、速度快的优点.但它仍存在如下缺点：1）终止判据对逼近误差的估计精度偏低;2）只适用于单输出问题.本文提出了适用于多输出问题且具有更高逼近精度的自适应稀疏伪谱逼近新方法.本文首先提出了新型终止判据及基于此新型终止判据的自适应稀疏伪谱逼近新方法,并以命题的形式证明了新型终止判据相比于现有终止判据具有更高的估计精度,从而使基于此的逼近函数精度更接近于预期精度;进而,本文基于指标集的统一策略和新型终止判据,提出了适用于多输出问题的自适应稀疏伪谱逼近新方法,该方法因能充分利用各输出变量的抽样结果,具有比将单输出方法直接推广到多输出问题更高的计算效率.多个算例验证了本文所提出新方法的有效性和正确性.     

GLOBAL CONVERGENCE AND IMPLEMENTATION OF NGTN METHOD FOR SOWING LARGE-SCALE SMRSE NONLINEAR PROGRAMMING PROBLEMS

1. IntroductionConsider the following NLP problemwhere the function f: Re --+ RI and gi: Re - R', j E J are twice continuously dtherentiable.In particular, we discuss the cajse, where the nUmber of variables and the nUmber of constraintsin (1.1) are large and second derivatives in (1.1) are sparse.There are some methods whiCh can solve largesscale problems, e.g. Lancelot in [2] andTDSQPLM in [9]. But they can not take adVantage of sparse structtire of the problem. A newefficient meth…     

Sparse approximate solutions to stochastic Galerkin equations

In this Note, we formulate a sparse Krylov-based algorithm for solving large-scale linear systems of algebraic equations arising from the discretization of randomly parametrized (or stochastic) elliptic partial differential equations (SPDEs). We analyze the proposed sparse conjugate gradient (CG) algorithm within the framework of inexact Krylov subspace methods, prove its convergence and study its abstract computational cost. Numerical studies conducted on stochastic diffusion models show that the proposed sparse CG algorithm outperforms the classical CG method when the sought solutions admit a sparse representation in a polynomial chaos basis. In such cases, the sparse CG algorithm recovers almost exactly the sparsity pattern of the exact solutions, which enables accelerated convergence. In the case when the SPDE solution does not admit a sparse representation, the convergence of the proposed algorithm is very similar to the classical CG method.     

ENHANCED BLOCK-SPARSE SIGNAL RECOVERY PERFORMANCE VIA TRUNCATED e2/e1-2 MINIMIZATION

In this paper, we investigate truncated $ℓ_2/ℓ_{1−2}$ minimization and its associated alternating direction method of multipliers (ADMM) algorithm for recovering the block sparse signals. Based on the block restricted isometry property (Block-RIP), a theoretical analysis is presented to guarantee the validity of proposed method. Our theoretical results not only show a less error upper bound, but also promote the former recovery condition of truncated ℓ₁₋₂ method for sparse signal recovery. Besides, the algorithm has been compared with some state-of-the-art algorithms and numerical experiments have shown excellent performances on recovering the block sparse signals.     

Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method

In order to precondition a sparse symmetric positive definite matrix, its approximate inverse is examined, which is represented as the product of two sparse mutually adjoint triangular matrices. In this way, the solution of the corresponding system of linear algebraic equations (SLAE) by applying the preconditioned conjugate gradient method (CGM) is reduced to performing only elementary vector operations and calculating sparse matrix-vector products. A method for constructing the above preconditioner is described and analyzed. The triangular factor has a fixed sparsity pattern and is optimal in the sense that the preconditioned matrix has a minimum K-condition number. The use of polynomial preconditioning based on Chebyshev polynomials makes it possible to considerably reduce the amount of scalar product operations (at the cost of an insignificant increase in the total number of arithmetic operations). The possibility of an efficient massively parallel implementation of the resulting method for solving SLAEs is discussed. For a sequential version of this method, the results obtained by solving 56 test problems from the Florida sparse matrix collection (which are large-scale and ill-conditioned) are presented. These results show that the method is highly reliable and has low computational costs.     

Inexact trust region PGC method for large sparse unconstrained optimization

We present an algorithm, partitioning group correction (PGC) algorithm based on trust region and conjugate gradient method, for large-scale sparse unconstrained optimization. In large sparse optimization, computing the whole Hessian matrix and solving the Newton-like equations at each iteration can be considerably expensive when a trust region method is adopted. The method depends on a symmetric consistent partition of the columns of the Hessian matrix and an inaccurate solution to the Newton-like equations by conjugate gradient method. And we allow that the current direction exceeds the trust region bound if it is a good descent direction. Besides, we studies a method dealing with some sparse matrices having a dense structure part. Some good convergence properties are kept and we contrast the computational behavior of our method with that of other algorithms. Our numerical tests show that the algorithm is promising and quite effective, and that its performance is comparable to or better than that of other algorithms available.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

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)     

Locally Sparse Estimator for Functional Linear Regression Models

A new locally sparse (i.e., zero on some subregions) estimator for coefficient functions in functional linear regression models is developed based on a novel functional regularization technique called “fSCAD.” The nice shrinkage property of fSCAD allows the proposed estimator to locate null subregions of coefficient functions without over shrinking nonzero values of coefficient functions. Additionally, a roughness penalty is incorporated to control the roughness of the locally sparse estimator. Our method is theoretically sounder and computationally simpler than existing methods. Asymptotic analysis reveals that the proposed estimator is consistent and can identify null subregions with probability tending to one. Extensive simulations confirm the theoretical analysis and show excellent numerical performance of the proposed method. Practical merit of locally sparse modeling is demonstrated by two real applications. Supplemental materials for the article are available online.     

Efficient Distributed Estimation of High-dimensional Sparse Precision Matrix for Transelliptical Graphical Models

In this paper,distributed estimation of high-dimensional sparse precision matrix is proposed based on the debiased D-trace loss penalized lasso and the hard threshold method when samples are distributed into different machines for transelliptical graphical models.At a certain level of sparseness,this method not only achieves the correct selection of non-zero elements of sparse precision matrix,but the error rate can be comparable to the estimator in a non-distributed setting.The numerical results further prove that the proposed distributed method is more effective than the usual average method.     

A fast LU update for linear programming

This paper discusses sparse matrix kernels of simplex-based linear programming software. State-of-the-art implementations of the simplex method maintain an LU factorization of the basis matrix which is updated at each iteration. The LU factorization is used to solve two sparse sets of linear equations at each iteration. We present new implementation techniques for a modified Forrest-Tomlin LU update which reduce the time complexity of the update and the solution of the associated sparse linear systems. We present numerical results on Netlib and other real-life LP models.     

A novel approach to solve linear systems arising from BEM using fast wavelet transforms

This paper uses Daubechies orthogonal wavelets to change dense and fully populated matrices of boundary element method (BEM) systems into sparse and semi‐banded matrices. Then a novel algorithm based on hierarchical nature of multiresolution analysis is introduced to solving resultant sparse linear systems. This algorithm decomposes NS‐form of transformed parent matrix into descendant systems with reduced sizes and solves them iteratively using GMRES algorithm. Both parts, changing dense matrices to sparse systems and the novel solver, can be added as a black box to the existing BEM codes. Transforming matrices into wavelet space needs less time than saved by solving sparse large systems. Numerical results with a precise study on sensitivity of solution for physical variables to the thresholding parameter, and savings in computer time and memory are presented. Also, the suitable value for thresholding parameter is recommended for elasticity problems. The results indicate that the proposed method is efficient for large problems. Copyright © 2009 John Wiley & Sons, Ltd.     

A gradient projection method for the sparse signal reconstruction in compressive sensing

Many problems arising from machine learning, compressive sensing, linear inverse problem, and statistical inference involve finding sparse solutions to under-determined or ill-conditioned equations. In this paper, a gradient projection method is proposed to recover sparse signal in compressive sensing by solving the nonlinear convex constrained equations. The global convergence is established with the backtracking line search. Preliminary numerical experiments coping with the sparse signal reconstruction in compressive sensing are performed, which show that the proposed method is very effective and stable.     

A projected conjugate gradient method for sparse minimax problems

A new method for nonlinear minimax problems is presented. The method is of the trust region type and based on sequential linear programming. It is a first order method that only uses first derivatives and does not approximate Hessians. The new method is well suited for large sparse problems as it only requires that software for sparse linear programming and a sparse symmetric positive definite equation solver are available. On each iteration a special linear/quadratic model of the function is minimized, but contrary to the usual practice in trust region methods the quadratic model is only defined on a one dimensional path from the current iterate to the boundary of the trust region. Conjugate gradients are used to define this path. One iteration involves one LP subproblem and requires three function evaluations and one gradient evaluation. Promising numerical results obtained with the method are presented. In fact, we find that the number of iterations required is comparable to that of state-of-the-art quasi-Newton codes.Research supported by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Natural Science Research Council.     

Preconditioned iterative methods on sparse subspaces

When some rows of the system matrix and a preconditioner coincide, preconditioned iterations can be reduced to a sparse subspace. Taking advantage of this property can lead to considerable memory and computational savings. This is particularly useful with the GMRES method. We consider the iterative solution of a discretized partial differential equation on this sparse subspace. With a domain decomposition method and a fictitious domain method the subspace corresponds a small neighborhood of an interface. As numerical examples we solve the Helmholtz equation using a fictitious domain method and an elliptic equation with a jump in the diffusion coefficient using a separable preconditioner.     

An Exterior Newton Method for Strictly Convex Quadratic Programming

We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.     

Adjusted Sparse Tensor Product Spectral Galerkin Method for Solving Pseudodifferential Equations on the Sphere with Random Input Data

An adjusted sparse tensor product spectral Galerkin approximation method based on spherical harmonics is introduced and analyzed for solving pseudodifferential equations on the sphere with random input data. These equations arise from geodesy where the sphere is taken as a model of the earth. Numerical solutions to the corresponding \(k\)-th order statistical moment equations are found in adjusted sparse tensor approximation spaces which are accordingly designed to the regularity of the data and the equation. Established convergence theorem shows that the adjusted sparse tensor Galerkin discretization is superior not only to the full tensor product but also to the standard sparse tensor counterpart when the statistical moments of the data are of mixed unequal regularity. Numerical experiments illustrate our theoretical results.

     

A novel robust principal component analysis method for image and video processing

The research on the robust principal component analysis has been attracting much attention recently. Generally, the model assumes sparse noise and characterizes the error term by the λ₁-norm. However, the sparse noise has clustering effect in practice so using a certain λ_p-norm simply is not appropriate for modeling. In this paper, we propose a novel method based on sparse Bayesian learning principles and Markov random fields. The method is proved to be very effective for low-rank matrix recovery and contiguous outliers detection, by enforcing the low-rank constraint in a matrix factorization formulation and incorporating the contiguity prior as a sparsity constraint. The experiments on both synthetic data and some practical computer vision applications show that the novel method proposed in this paper is competitive when compared with other state-of-the-art methods.     

A Sparse Grid Stochastic Collocation Discontinuous Galerkin Method for Constrained Optimal Control Problem Governed by Random Convection Dominated Diffusion Equations

A sparse grid stochastic collocation method combined with discontinuous Galerkin method is developed for solving convection dominated diffusion optimal control problem with random coefficients. By the optimal control theory, an optimality system is obtained for the problem, which consists of a state equation, a co-state equation and an inequality. Based on finite dimensional noise assumption of random field, the random coefficients are assumed to have finite term expansions depending on a finite number of mutually independent random variables in the probability space. An approximation scheme is established by using a discontinuous Galerkin method for the physical space and a sparse grid stochastic collocation method based on the Smolyak construction for the probability space, which leads to the solution of uncoupled deterministic problems. A priori error estimates are derived for the state, co-state and control variables. Numerical experiments are presented to illustrate the theoretical results.