检索结果-内蒙古大学图书馆

Restrictively preconditioned chebyshev method for solving systems of linear equations

JOURNAL OF ENGINEERING MATHEMATICS 2015年第1期93卷 61-76页

作者： Wang, Zeng-Qi Shanghai Jiao Tong Univ Key Lab Sci & Engn Comp Dept Math Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Key Lab Sci & Engn Comp Minist Educ Shanghai 200240 Peoples R China

The restrictive preconditioning technique applied to chebyshev semi-iterative methods for solving a nonsingular system of linear equations is studied. Motivated by the fact that linear systems involving a preconditioner are solved inexactly at each step, we present the inexact restrictively preconditioned chebyshev method. The convergence behaviors of the new methods are analyzed, particularly for solving two-by-two block systems. Numerical experiments show that the new methods may be more efficient than the restrictively preconditioned conjugate gradient method in the presence of inexactness. Moreover, the inexact restrictively preconditioned chebyshev method is a strong competitor to the block upper triangular preconditioned GMRES and flexible GMRES methods for solving generalized saddle point problems.

关键词： chebyshev semi-iterative method Inexact iteration Nonsymmetric linear system Restrictive preconditioning

来源：评论

学校读者我要写书评

暂无评论

A comparative study on low-memory iterative solvers for FFT-based homogenization of periodic media

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2016年 321卷 151-168页

作者： Mishra, Nachiketa Vondrejc, Jaroslav Zeman, Jan Czech Tech Univ Fac Civil Engn Dept Mech Thakurova 7 Prague 16629 6 Czech Republic Tech Univ Carolo Wilhelmina Braunschweig Inst Comp Sci Muhlenpfordtstr 23 D-38106 Braunschweig Germany

In this paper, we assess the performance of four iterative algorithms for solving non-symmetric rank-deficient linear systems arising in the FFT-based homogenization of heterogeneous materials defined by digital images. Our framework is based on the Fourier-Galerkin method with exact and approximate integrations that has recently been shown to generalize the Lippmann-Schwinger setting of the original work by Moulinec and Suquet from 1994. It follows from this variational format that the ensuing system of linear equations can be solved by general-purpose iterative algorithms for symmetric positive-definite systems, such as the Richardson, the Conjugate gradient, and the chebyshev algorithms, that are compared here to the Eyre-Milton scheme - the most efficient specialized method currently available. Our numerical experiments, carried out for two-dimensional elliptic problems, reveal that the Conjugate gradient algorithm is the most efficient option, while the Eyre-Milton method performs comparably to the chebyshev semi-iteration. The Richardson algorithm, equivalent to the still widely used original Moulinec-Suquet solver, exhibits the slowest convergence. Besides this, we hope that our study highlights the potential of the well-established techniques of numerical linear algebra to further increase the efficiency of FFT-based homogenization methods. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Numerical homogenization Fourier-Galerkin method Fast Fourier Transform Guaranteed bounds Richardson iteration Conjugate gradient algorithm chebyshev semi-iterative method Eyre-Milton scheme

来源：评论

学校读者我要写书评

暂无评论

Approximating dominant singular triplets of large sparse matrices via modified moments

引用

NUMERICAL ALGORITHMS 1996年第1-2期13卷 123-152页

作者： Varadhan, S Berry, MW Golub, GH UNIV TENNESSEE DEPT COMP SCI KNOXVILLE TN 37996 USA STANFORD UNIV DEPT COMP SCI STANFORD CA 94305 USA

A procedure for determining a few of the largest singular values and corresponding singular vectors of large sparse matrices is presented. Equivalent eigensystems are solved using a technique originally proposed by Golub and Kent based on the computation of modified moments. The asynchronicity in the computations of moments and eigenvalues makes this method attractive for parallel implementations on a network of workstations. Although no obvious relationship between modified moments and the corresponding eigenvectors is known to exist, a scheme to approximate both eigenvalues and eigenvectors (and subsequently singular values and singular vectors) has been produced. This scheme exploits both modified moments in conjunction with the chebyshev semi-iterative method and deflation techniques to produce approximate eigenpairs of the equivalent sparse eigensystems. The performance of an ANSI-C implementation of this scheme on a network of UNIX workstations and a 256-processor Gray no is presented.

关键词： chebyshev semi-iterative method modified moments singular value decomposition sparse matrices

来源：评论

学校读者我要写书评

暂无评论

A chebyshev semi-iterative Approach for Accelerating Projective and Position-based Dynamics

引用

ACM TRANSACTIONS ON GRAPHICS 2015年第6期34卷 1-9页

作者： Wang, Huamin Ohio State Univ Columbus OH 43210 USA

In this paper, we study the use of the chebyshev semi-iterative approach in projective and position-based dynamics. Although projective dynamics is fundamentally nonlinear, its convergence behavior is similar to that of an iterative method solving a linear system. Because of that, we can estimate the "spectral radius" and use it in the chebyshev approach to accelerate the convergence by at least one order of magnitude, when the global step is handled by the direct solver, the Jacobi solver, or even the Gauss-Seidel solver. Our experiment shows that the combination of the chebyshev approach and the direct solver runs fastest on CPU, while the combination of the chebyshev approach and the Jacobi solver outperforms any other combination on GPU, as it is highly compatible with parallel computing. Our experiment further shows position-based dynamics can be accelerated by the chebyshev approach as well, although the effect is less obvious for tetrahedral meshes. The whole approach is simple, fast, effective, GPU-friendly, and has a small memory cost.

关键词： Jacobi method chebyshev semi-iterative method position-based dynamics projective dynamics parallel computing

来源：评论

学校读者我要写书评

暂无评论

A chebyshev semi-iterative Approach for Accelerating Projective and Position-based Dynamics

A Chebyshev Semi-Iterative Approach for Accelerating Project...

引用

ACM SIGGRAPH Asia Conference

作者： Wang, Huamin Ohio State Univ Columbus OH 43210 USA

ISBN: (纸本)9781450333313

关键词： Jacobi method chebyshev semi-iterative method position-based dynamics projective dynamics parallel computing

来源：评论

学校读者我要写书评

暂无评论

Parallel iterative Solvers for Real-time Elastic Deformations 18

Parallel Iterative Solvers for Real-time Elastic Deformation...

引用

11th ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia (SA)

作者： Fratarcangeli, Marco Wang, Huamin Yang, Yin Chalmers Univ Technol Gothenburg Sweden Ohio State Univ Columbus OH 43210 USA Univ New Mexico Albuquerque NM 87131 USA

ISBN: (纸本)9781450360265

Physics-based animation of elastic materials allows to simulate dynamic deformable objects such as fabrics, human tissue, hair, etc. Due to their complex inner mechanical behaviour, it is difficult to replicate their motions interactively and accurately at the same time. This course introduces students and practitioners to several parallel iterative techniques to tackle this problem and achieve elastic deformations in real-time. We focus on techniques for applications such as video games and interactive design, with fixed and small hard time budgets available for physically-based animation, and where responsiveness and stability are often more important than accuracy, as long as the results are believable. The course focuses on solvers able to fully exploit the computational capabilities of modern GPU architectures, effectively solving systems of hundreds of thousands of nonlinear equations in a matter of few milliseconds. The course introduces the basic concepts concerning physics-based elastic objects, and provide an overview of the different types of numerical solvers available in the literature. Then, we show how some variants of traditional solvers can address real-time animation and assess them in terms of accuracy, robustness and performance. Practical examples are provided throughout the course, in particular how to apply the depicted solvers to Projective Dynamics and Position-based Dynamics, two recent and popular physics models for elastic materials.

关键词： Nonlinear Optimization Hyperelasticity Jacobi method chebyshev semi-iterative method Multi-color Gauss-Seidel method Projective Dynamics Position Based Dynamics Parallel Computing GPU Acceleration

来源：评论

学校读者我要写书评

暂无评论

LSRN: A PARALLEL iterative SOLVER FOR STRONGLY OVER- OR UNDERDETERMINED SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2014年第2期36卷 C95-C118页

作者： Meng, Xiangrui Saunders, Michael A. Mahoney, Michael W. Stanford Univ ICME Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Syst Optimizat Lab Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA

We describe a parallel iterative least squares solver named LSRN that is based on random normal projection. LSRN computes the min-length solution to min(x is an element of Rn) vertical bar vertical bar Ax - b vertical bar vertical bar(2), where A is an element of R-mxn with m >> n or m << n, and where A may be rank-deficient. Tikhonov regularization may also be included. Since A is involved only in matrix-matrix and matrix-vector multiplications, it can be a dense or sparse matrix or a linear operator, and LSRN automatically speeds up when A is sparse or a fast linear operator. The preconditioning phase consists of a random normal projection, which is embarrassingly parallel, and a singular value decomposition of size inverted right perpendicular gamma min(m, n) inverted left perpendicular x min(m, n), where gamma is moderately larger than 1, e.g., gamma = 2. We prove that the preconditioned system is well-conditioned, with a strong concentration result on the extreme singular values, and hence that the number of iterations is fully predictable when we apply LSQR or the chebyshev semi-iterative method. As we demonstrate, the chebyshev method is particularly efficient for solving large problems on clusters with high communication cost. Numerical results show that on a shared-memory machine, LSRN is very competitive with LAPACK's DGELSD and a fast randomized least squares solver called Blendenpik on large dense problems, and it outperforms the least squares solver from SuiteSparseQR on sparse problems without sparsity patterns that can be exploited to reduce fill-in. Further experiments show that LSRN scales well on an Amazon Elastic Compute Cloud cluster.

关键词： linear least squares overdetermined system underdetermined system rank-deficient minimum-length solution LAPACK sparse matrix iterative method preconditioning LSQR chebyshev semi-iterative method Tikhonov regularization ridge regression parallel computing random projection random sampling random matrix randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

AN INCOMPLETE FACTORIZATION iterative TECHNIQUE FOR ELLIPTIC-EQUATIONS

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1990年第1-4期35卷 245-259页

作者： KRISHNA, LB Department of Mathematical Sciences The University of Akron Akron Ohio 44325 United States

This paper describes efficient iterative techniques for solving the large sparse symmetric linear systems that arise from application of finite difference approximations to self-adjoint elliptic equations. We use an incomplete factorization technique with the method of D'Yakonov type, generalized conjugate gradient and chebyshev semi-iterative methods. We compare these methods with numerical examples. Bounds for the A-norm of the error vector of the chebyshev semi-iterative method in terms of the spectral radius of the iteration matrix are derived. © 1990, Taylor & Francis Group, LLC. All rights reserved.

关键词： chebyshev semi-iterative method Incomplete factorization spectral radius

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：