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

Maximum-weight-basis preconditioners

numerical linear algebra WITH applications 2004年第8-9期11卷 695-721页

作者： Boman, EG Chen, D Hendrickson, B Toledo, S Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Sandia Natl Labs Albuquerque NM 87185 USA

This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based oil a simple idea: we construct M by go simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in all unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n + t(2)) nonzeros, where n is the dimension of the matrix and 1less than or equal totless than or equal ton is a parameter that one can choose. Their construction is efficient and gauarantees that the condition number of the preconditioned system is O(n(2)/t(2)) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem;we show the combinatorial structure of the preconditioners and we present encouraging convergence results. Copyright (C) 2004 John Wiley Sons, Ltd.

关键词： sparse linear solvers preconditioning support theory support preconditioners maximum-weight bases matroids

来源：评论

学校读者我要写书评

暂无评论

Iterative methods for Toeplitz Systems

引用

丛书名： numerical mathematics and scientific computation

2004年

作者： Michael K Ng

ISBN: (数字)9781383020823

ISBN: (纸本)9780198504207

Toeplitz and Toeplitz-related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. This book deals primarily with iterative methods for solving Toeplitz and Toeplitz-related linear systems, discussing both the algorithms and their convergence theories. A basic knowledge of real analysis, elementary numerical analysis and linear algebra is assumed. The first part of the book (chapters one and two) gives a brief review of some terms and results in linear algebra and the conjugate gradient method, which are important topics for handling the mathematics later on in the book. The second part of the book (chapters three to seven) presents the theory of using iterative methods for solving Toeplitz and Toeplitz-related systems. The third part of the book (chapters eight to twelve) presents recent results from applying the use of iterative methods in different fields of applications, such as partial differential equations, signal and image processing, integral equations and queuing networks. These chapters provide research and application-oriented readers with a thorough understanding of using iterative methods, enabling them not only to apply these methods to the problems discussed but also to derive and analyse new methods for other types of problems and applications.

关键词： Electronics and Communications Engineering Mathematical and Statistical Physics Applied Mathematics

来源：评论

学校读者我要写书评

暂无评论

On doubly structured matrices and pencils that arise in linear response theory

On doubly structured matrices and pencils that arise in line...

引用

GAMM Workshop on Applied and numerical linear algebra

作者： Mehl, C Mehrmann, V Xu, HG Tech Univ Berlin Inst Math D-10623 Berlin Germany Univ Kansas Dept Math Lawrence KS 66045 USA

We discuss matrix pencils with a double symmetry structure that arise in the Hartree-Fock model in quantum chemistry. We derive anti-triangular condensed forms from which the eigenvalues can be read off. Ideally these would be condensed forms under unitary equivalence transformations that can be turned into stable (structure preserving) numerical methods. For the pencils under consideration this is a difficult task and not always possible. We present necessary and sufficient conditions when this is possible. If this is not possible then we show how we can include other transformations that allow to reduce the pencil to an almost anti-triangular form. (C) 2003 Elsevier Inc. All rights reserved.

关键词： self-adjoint matrix skew-adjoint matrix matrix pencil Hartree-Fock model random phase approximation anti-triangular form canonical form condensed form Skew-Hamiltonian/Hamiltonian pencil

来源：评论

学校读者我要写书评

暂无评论

Capon-LS for model order selection of multicomponent interferometric SAR signals

引用

IEE PROCEEDINGS-RADAR SONAR AND NAVIGATION 2004年第5期151卷 299-305页

作者： Bordoni, F Gini, F Verrazzani, L Univ Pisa Dipartimento Ingn Informaz I-56122 Pisa Italy

The authors address the problem of estimating the number of components in a multibaseline interferometric synthetic aperture radar (InSAR) signal, corrupted by complex correlated multiplicative noise, in the presence of the layover phenomenon. The appearance of multiplicative noise, termed `speckle', makes this problem very atypical. In fact, all the approaches proposed in literature have been applied to constant amplitude sinusoidal signals. In particular, the information theoretic criteria (ITC) have been conceived for estimating the number of signal components embedded in additive white noise. In this case, the problem is equivalent to the estimation of the multiplicity of the smallest eigenvalues of the data covariance matrix. In the presence of multiplicative noise, the signal eigenvalues spectrum changes. Consequently, the classic ITC methods operate under model mismatch. In a previous work, the authors investigated their robustness to speckle. An ad hoc algorithm for model order selection, based on Capon and least squares methods is developed. Its performance is analysed via Monte Carlo simulation and compared with those of classic ITC.

关键词： order selection model covariance matrices Monte Carlo simulation additive white noise correlated multiplicative noise layover phenomenon speckle noise data covariance matrix linear algebra (numerical analysis) ad hoc algorithm Capon-LS multicomponent interferometric SAR signal Radar equipment, systems and applications Monte Carlo methods Interpolation and function approximation (numerical analysis) constant amplitude sinusoidal signal eigenvalue spectrum eigenvalues and eigenfunctions information theoretic criteria interferometry correlation theory multibaseline interferometric synthetic aperture radar signal synthetic aperture radar white noise signal component estimation least squares approximations Capon least squares method

来源：评论

学校读者我要写书评

暂无评论

algebraic Schwarz methods for the numerical solution of Markov chains

引用

linear algebra AND ITS applications 2004年 386卷 67-81页

作者： Marek, I Szyld, DB Temple Univ 038 16 Dept Math Philadelphia PA 19122 USA Czech Inst Technol Sch Civil Engn Prague 16629 6 Czech Republic

The convergence of additive and multiplicative Schwarz methods for computing certain characteristics of Markov chains such as stationary probability vectors and mean first passage matrices is studied. The main result is a convergence theorem for multiplicative Schwarz iterations when applied to singular systems. As a byproduct, a convergence result for alternating iterations is also obtained. It is also shown that, when the Markov chain is ergodic, additive and multiplicative Schwarz methods can be applied to the nonsingular systems that result from reducing the equations. The so-called coarse grid corrections are also studied. (C) 2004 Elsevier Inc. All rights reserved.

关键词： Schwarz methods singular M-matrices Markov chains stationary probability vectors iterative methods

来源：评论

学校读者我要写书评

暂无评论

Symbolic state-space exploration and numerical analysis of state-sharing composed models

引用

linear algebra AND ITS applications 2004年 386卷 137-166页

作者： Derisavi, S Kemper, P Sanders, WH Univ Illinois Coordinated Sci Lab Elect & Comp Engn Dept Urbana IL 61801 USA Univ Illinois Comp Sci Dept Urbana IL 61801 USA Univ Dortmund D-44221 Dortmund Germany

The complexity of stochastic models of real-world systems is usually managed by abstracting details and structuring models in a hierarchical manner. Systems are often built by replicating and joining subsystems, making possible the creation of a model structure that yields lumpable state spaces. This fact has been exploited to facilitate model-based numerical analysis. Likewise, recent results on model construction suggest that decision diagrams can be used to compactly represent large continuous time Markov chains (CTMCs). In this paper, we present an approach that combines and extends these two approaches. In particular, we propose methods that apply to hierarchically structured models with hierarchies based on sharing state variables. The hierarchy is constructed in a way that exposes structural symmetries in the constructed model, thus facilitating lumping. In addition, the methods allow one to derive a symbolic representation of the associated CTMC directly from the given model without the need to compute and store the overall state space or CTMC explicitly. The resulting representation of a generator matrix allows the analysis of large CTMCs in lumped form. The efficiency of the approach is demonstrated with the help of two example models. (C) 2004 Published by Elsevier Inc.

关键词： multi-valued decision diagrams Matrix diagrams numerical analysis symbolic state-space exploration

来源：评论

学校读者我要写书评

暂无评论

Second order sufficient conditions for time-optimal bang-bang control

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2004年第6期42卷 2239-2263页

作者： Maurer, H Osmolovskii, NP Univ Munster Inst Numer Math D-48149 Munster Germany Moscow State Civil Engn Univ MISI Dept Appl Math Moscow Russia

We study second order sufficient optimality conditions (SSC) for optimal control problems with control appearing linearly. Specifically, time-optimal bang-bang controls will be investigated. In [N. P. Osmolovskii, Sov. Phys. Dokl., 33 (1988), pp. 883-885;theory of Higher Order Conditions in Optimal Control, Doctor of Sci. thesis, Moscow, 1988 ( in Russian);Russian J. Math. Phys., 2 (1995), pp. 487-516;Russian J. Math. Phys., 5 (1997), pp. 373-388;Proceedings of the conference "Calculus of Variations and Optimal Control," Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 198-216;A. A. Milyutin and N. P. Osmolovskii, Calculus of Variations and Optimal Control, Transl. Math. Monogr. 180, AMS, Providence, RI, 1998], SSC have been developed in terms of the positive definiteness of a quadratic form on a critical cone or subspace. No systematical numerical methods for verifying SSC are to be found in these papers. In the present paper, we study explicit representations of the critical subspace. This leads to an easily implementable test for SSC in the case of a bang-bang control with one or two switching points. In general, we show that the quadratic form can be simplified by a transformation that uses a solution to a linear matrix differential equation. Particular conditions even allow us to convert the quadratic form to perfect squares. Three numerical examples demonstrate the numerical viability of the proposed tests for SSC.

关键词： optimal bang-bang control second order sufficient conditions Q-transformation to perfect squares numerical verification applications

来源：评论

学校读者我要写书评

暂无评论

algebraic Schwarz methods for the numerical solution of Markov chains

Algebraic Schwarz methods for the numerical solution of Mark...

引用

11th ILAS conference

作者： Marek, I Szyld, DB Temple Univ 038 16 Dept Math Philadelphia PA 19122 USA Czech Inst Technol Sch Civil Engn Prague 16629 6 Czech Republic

关键词： Schwarz methods singular M-matrices Markov chains stationary probability vectors iterative methods

来源：评论

学校读者我要写书评

暂无评论

algebraic multigrid methods for constrained linear systems with applications to contact problems in solid mechanics

引用

numerical linear algebra WITH applications 2004年第2-3期11卷 141-153页

作者： Adams, MF Sandia Natl Labs Livermore CA 94551 USA

This paper develops a general framework for applying algebraic multigrid techniques to constrained systems of linear algebraic equations that arise in applications with discretized PDEs. We discuss constraint coarsening strategies for constructing multigrid coarse grid spaces and several classes of multigrid smoothers for these systems. The potential of these methods is investigated with their application to contact problems in solid mechanics. Published in 2004 by John Wiley Sons, Ltd.

关键词： algebraic multigrid multigrid methods saddle point problems parallel multigrid contact contact in solid mechanics

来源：评论

学校读者我要写书评

暂无评论

Symbolic state-space exploration and numerical analysis of state-sharing composed models

Symbolic state-space exploration and numerical analysis of s...

引用

11th ILAS conference

关键词： multi-valued decision diagrams Matrix diagrams numerical analysis symbolic state-space exploration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：