This paper presents, analyzes, and tests a row-action method for solving the regularized linear programming problem: minimize 1/2parallel toxparallel to(2)(2) + alphac(T)x subject to Ax greater than or equal to b, whe...
详细信息
This paper presents, analyzes, and tests a row-action method for solving the regularized linear programming problem: minimize 1/2parallel toxparallel to(2)(2) + alphac(T)x subject to Ax greater than or equal to b, where a is a given positive constant. The proposed method is based on the observation that the dual of this problem has the form: maximize b(T)y - 1/2parallel to A(T) y - alphacparallel to(2)(2) subject to y greater than or equal to 0. and if y(alpha) solves the dual then the point x(alpha) A(T)y(alpha) - alphac provides the unique solution of the primal. Maximizing the dual objective function by changing one variable at a time results in an effective row-action method which is suitable for solving large sparse problems. One aim of this paper is to clarify the convergence properties of the proposed scheme. Let Y-k denote the estimated dual solution at the end of the kth iteration, and let X-k = A(T) y(k) - alphac denote the corresponding primal estimate. It is proved that the sequence {x(k)} converges to x(alpha), while the sequence {y(k)} converges to a point y(alpha) that solves the dual. The only assumption which is needed in order to establish these claims is that the feasible region is not empty. Yet perhaps the more striking features of the algorithm are related to temporary situations in which it attempts to solve an inconsistent system. In such cases the sequence {y(k)} obeys the rule: y(k) = u(k) + kv. where {u(k)} is a fastly converging sequence and v is a fixed vector that satisfies A(T)v = 0 and b(T)v > 0. So the sequence {X-k} is almost unchanged for many iterations, The paper ends with numerical experiments that illustrate the effects of this phenomenon and the close links with Kaczmarz's SOR method. (C) 2002 Elsevier Science Inc. All rights reserved.
The proceedings contain 64 papers. The special focus in this conference is on Quasi-Monte Carlo methods, Robust Iterative Solution methods, Control and Uncertain Systems. The topics include: An introduction to the the...
ISBN:
(纸本)3540006087
The proceedings contain 64 papers. The special focus in this conference is on Quasi-Monte Carlo methods, Robust Iterative Solution methods, Control and Uncertain Systems. The topics include: An introduction to the theory of plausible and paradoxical reasoning;comparison of ten methods for the solution of large and sparse linearalgebraic systems;variable-coefficient difference schemes for quasilinear evolution problems;additive schemes for systems of time-dependent equations of mathematical physics;geometry of polynomials and numerical analysis;hybrid Monte Carlo methods for matrix computation;a new efficient algorithm for generating the scrambled sobol’ sequence;generating and testing the modified halton sequences;parallel importance separation and adaptive Monte Carlo algorithms for multiple integrals;Monte Carlo and quasi-Monte Carlo algorithms for the barker-ferry equation with low complexity;on some weight Monte Carlo methods for investigating the asymptotical behavior of solution of the transfer equation;a Monte Carlo approach for finding more than one eigenpair;a new class of grid-free Monte Carlo algorithms for elliptic boundary value problems;Monte-Carlo integration using cryptographically secure pseudo-random generator;galerkin and control volume finite element methods for large scale air pollution simulations;robust preconditioners for saddle point problems;on a multigrid adaptive refinement solver for saturated non-Newtonian flow in porous media;on a multigrid eigensolver for linear elasticity problems;discrete methods for optimal control problems and numerical schemes of higher order for a class of nonlinear control systems.
This volume describes for the first time in monograph form important applications in numericalmethods of linearalgebra. The author presents new material and extended results from recent papers in a very readable sty...
详细信息
ISBN:
(数字)9781470431457
ISBN:
(纸本)9780821832479
This volume describes for the first time in monograph form important applications in numericalmethods of linearalgebra. The author presents new material and extended results from recent papers in a very readable style. The main goal of the book is to study the behavior of the resolvent of a matrix under the perturbation by low rank matrices. Whereas the eigenvalues (the poles of the resolvent) and the pseudospectra (the sets where the resolvent takes large values) can move dramatically under such perturbations, the growth of the resolvent as a matrix-valued meromorphic function remains essentially unchanged. This has practical implications to the analysis of iterative solvers for large systems of linearalgebraic equations. First, the book introduces the basics of value distribution theory of meromorphic scalar functions. It then introduces a new nonlinear tool for linearalgebra, the total logarithmic size of a matrix, which allows for a nontrivial generalization of Rolf Nevanlinna's characteristic function from the scalar theory to matrix- and operator-valued functions. In particular, the theory of perturbations by low rank matrices becomes possible. As an example, if the spectrum of a normal matrix collapses under a low rank perturbation, there is always a compensation in terms of the loss of orthogonality of the eigenvectors. This qualitative phenomenon is made quantitative by using the new tool. applications are given to rational approximation, to the Kreiss matrix theorem, and to convergence of Krylov solvers. The book is intended for researchers in mathematics in general and especially for those working in numericallinearalgebra. Much of the book is understandable if the reader has a good background in linearalgebra and a first course in complex analysis.
In this paper we use the theory of Faber polynomials for solving N-dimensional linear initial value problems. In particular, we use Faber polynomials to approximate the evolution operator creating the so-called expone...
In this paper we use the theory of Faber polynomials for solving N-dimensional linear initial value problems. In particular, we use Faber polynomials to approximate the evolution operator creating the so-called exponential integrators. We also provide a consistence and convergence analysis. Some tests where we compare our methods with some Krylov exponential integrators are finally shown. Copyright (C) 2002 John Wiley Sons, Ltd.
Developing a comprehensive simulation model of a multi- body system (MBS) is not a trivial task, however, over the years many tools and techniques have been developed to make this task easy and less cumbersome. Many o...
详细信息
ISBN:
(纸本)1565552687
Developing a comprehensive simulation model of a multi- body system (MBS) is not a trivial task, however, over the years many tools and techniques have been developed to make this task easy and less cumbersome. Many of the innovations and advances have come in three areas;(i)modeling interface, (ii)efficient numerical formulations, and (iii)enhanced computational schemes. With the advent of powerful computational capabilities, the emphasis has shifted away from modeling innovation, to enhanced computational approaches. The ability to turn a model on its head and examine it form an analytical perspective, has yielded to powerful visualization tools that make sense of reams of numerical data generated by complex codes. Yet, the essential role of a simulation model, namely to provide a manageable representation of reality that can be useful in comprehending the phenomena, has not changed one iota. Presented here is a generic, unified. topologically based approach, which uses a minimal set of generalized coordinates, and a minimal set of constraint equations to completely model physical systems of significant complexity. The core formulation is based on well known graph theoretic methods, popular in linear network theory, and controller design theory, among other fields. The present formulation is built on the dual vector approach for dynamics championed by Andrew. Kesavan, and others. Later work (Baciu. McPhee) showed its applicability for dynamical analyses of multi-body systems (MBS). The authors have married this approach with a object oriented physically based modeling technique to enhance its usability and universal applicability. This paper outlines the characteristics of such an approach, through an actual implementation of a MBS closely integrated with a controller, with respect to real time nonlinear simulation applications.
SDP (SemiDefinite Programming) is one of the most attractive optimization models. It has many applications from various fields such as control theory, combinatorial and robust optimization, and quantum chemistry. The ...
详细信息
SDP (SemiDefinite Programming) is one of the most attractive optimization models. It has many applications from various fields such as control theory, combinatorial and robust optimization, and quantum chemistry. The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs based on primal-dual interior-point methods with the HRVW/KSH/M search direction. It is written in C++ with the help of LAPACK for numericallinearalgebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance for large scale problems through numerical experiments and comparisons with some other major software packages for general SDPs.
Modal behavior of a 2-D (square lattice geometry) antiguided vertical cavity surface emitting laser (VCSEL) array was studied numerically. The background of the numerical model of VCSEL array is scalar diffraction the...
详细信息
The proceedings contain 119 papers. The special focus in this conference is on Computational Finance, Economics, numericalmethods for Structured Systems and High Performance Environmental Computations. The topics inc...
ISBN:
(纸本)9783540401957
The proceedings contain 119 papers. The special focus in this conference is on Computational Finance, Economics, numericalmethods for Structured Systems and High Performance Environmental Computations. The topics include: Parallel computing method of valuing for multi-asset European option;a fuzzy approach to portfolio rebalancing with transaction costs;mining investment venture rules from insurance data based on decision tree;double auction in two-level markets;a set of data mining models to classify credit cardholder behavior;continuous time Markov decision processes with expected discounted total rewards;model on analysis of industrial relation based on the binary relation theory;multi-symplectic spectral methods for the sine-Gordon equation;a discrete approach for the inverse singular value problem in some quadratic group;a symplectic lanczos-type algorithm to compute the eigenvalues of positive definite Hamiltonian matrices;applying stabilization techniques to orthogonal gradient flows;coupling general circulation models on a meta-computer;optimal numerical realization of the energy balance equation for wind wave models;simulation of water exchange in enclosed water bodies;a baroclinic three dimensional numerical model applied to coastal lagoons;stochastic simulation of inhomogeneous metocean fields;performance comparison of process allocation schemes depending upon resource availability on grid computing environment;efficient load balancing by adaptive bypasses for the migration on the internet;generalization of the fast consistency algorithm to a grid with multiple high demand zones and linearalgebra computation benchmarks on a model grid platform.
暂无评论