OPAC - Pencarian Artikel Jurnal & Majalah Library USD
Menampilkan semua artikel (Halaman 695 dari 34166, Total: 341652 data)
Convergence of Polynomial Restart Krylov Methods for Eigenvalue Computations
klik untuk membaca file PDF
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 3) |
| Halaman | : | 492-515 |
| Abstrak | : | Krylov subspace methods have led to reliable and effective tools for resolving large-scale, non-Hermitian eigenvalue problems. Since practical considerations often limit the dimension of the approximating Krylov subspace, modern algorithms attempt to identify and condense significant components from the current subspace, encode them into a polynomial filter, and then restart the Krylov process with a suitably refined starting vector. In effect, polynomial filters dynamically steer low-dimensional Krylov spaces toward a desired invariant subspace through their action on the starting vector. The spectral complexity of nonnormal matrices makes convergence of these methods difficult to analyze, and these effects are further complicated by the polynomial filter process. The principal object of study in this paper is the angle an approximating Krylov subspace forms with a desired invariant subspace. Convergence analysis is posed in a geometric framework that is robust to eigenvalue ill-conditioning, yet remains relatively uncluttered. The bounds described here suggest that the sensitivity of desired eigenvalues exerts little influence on convergence, provided the associated invariant subspace is well-conditioned; ill-conditioning of unwanted eigenvalues plays an essential role. This framework also gives insight into the design of effective polynomial filters. Numerical examples illustrate the subtleties that arise when restarting non-Hermitian iterations. |
Reviving the Method of Particular Solutions
| Pengarang | : | Timo Betcke |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 3) |
| Halaman | : | 469-491 |
| Abstrak | : | Fox, Henrici, and Moler made famous a "method of particular solutions" for computing eigenvalues and eigenmodes of the Laplacian in planar regions such as polygons. We explain why their formulation of this method breaks down when applied to regions that are insufficiently simple and propose a modification that avoids these difficulties. The crucial changes are to introduce points in the interior of the region as well as on the boundary and to minimize a subspace angle rather than just a singular value or a determinant. Similar methods may be used to improve other "mesh-free" algorithms for a variety of computational problems. |
A Fast and Stable Solution Method for the Radiative Transfer Problem
| Pengarang | : | Per Edström |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 3) |
| Halaman | : | 447-468 |
| Abstrak | : | Radiative transfer theory considers radiation in turbid media and is used in a wide range of applications. This paper outlines a problem formulation and a solution method for the radiative transfer problem in multilayer scattering and absorbing media using discrete ordinate model geometry. A selection of different steps is brought together. The main contribution here is the synthesis of these steps, all of which have been used in different areas, but never all together in one method. First, all necessary steps to get a numerically stable solution procedure are treated, and then methods are introduced to increase the speed by a factor of several thousand. This includes methods for handling strongly forward-scattering media. The method is shown to be unconditionally stable, though the problem was previously considered numerically intractable. |
Canonical Forms for Hermitian Matrix Pairs under Strict Equivalence and Congruence
| Pengarang | : | Peter Lancaster |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 3) |
| Halaman | : | 407-443 |
| Abstrak | : | After a brief historical review and an account of the canonical forms attributed to Jordan and Kronecker, a systematic development is made of the simultaneous reduction of pairs of quadratic forms over the complex numbers and over the reals. These reductions are by strict equivalence and by congruence, and essentially complete proofs are presented. Some closely related results which can be derived from the canonical forms are also included. They concern simultaneous diagonalization, a new criterion for the existence of positive definite linear combinations of a pair of Hermitian matrices, and the canonical structures of matrices which are self-adjoint in an indefinite inner product. |
Critical Percolation on a Bethe Lattice Revisited
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 349-365 |
| Abstrak | : | We introduce the model of independent percolation on general graphs with emphasis on the Bethe lattice, for which we prove the existence of a phase transition with the precise calculation of the critical value, and derive the value of the critical exponents and . |
Adaptive Smoothed Aggregation (SA) Multigrid
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 317-346 |
| Abstrak | : | Substantial effort has been focused over the last two decades on developing multilevel iterative methods capable of solving the large linear systems encountered in engineering practice. These systems often arise from discretizing partial differential equations over unstructured meshes, and the particular parameters or geometry of the physical problem being discretized may be unavailable to the solver. Algebraic multigrid (AMG) and multilevel domain decomposition methods of algebraic type have been of particular interest in this context because of their promises of optimal performance without the need for explicit knowledge of the problem geometry. These methods construct a hierarchy of coarse problems based on the linear system itself and on certain assumptions about the smooth components of the error. For smoothed aggregation (SA) multigrid methods applied to discretizations of elliptic problems, these assumptions typically consist of knowledge of the near-kernel or near-nullspace of the weak form. This paper introduces an extension of the SA method in which good convergence properties are achieved in situations where explicit knowledge of the near-kernel components is unavailable. This extension is accomplished in an adaptive process that uses the method itself to determine near-kernel components and adjusts the coarsening processes accordingly. |
k Workers in a Circular Warehouse: A Random Walk on a Circle, without Passing
| Pengarang | : | PC. S. Sutisno |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 301-314 |
| Abstrak | : | We consider the problem of stochastic flow of multiple particles traveling on a closed loop, with a constraint that particles move without passing. We use a Markov chain description that reduces the problem to a generalized random walk on a hyperplane (with boundaries). By expressing positions via a moving reference frame, the geometry of the no-passing criteria is greatly simplified, with the resultant condition expressible as the coordinate system planes which bound the first orthant. To determine state transition probabilities, we decompose transitions into independent events and construct a digraph representation in which calculating transition probability is reduced to a shortest path determination on the digraph. The resultant decomposition digraph is self-converse, and we exploit that property to establish the necessary symmetries to find the stationary density for the process. |
Iterated Impact Dynamics of N-Beads on a Ring
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 273-300 |
| Abstrak | : | When N-beads slide along a frictionless hoop, their collision sequence gives rise to a dynamical system that can be studied via matrix products. It is of general interest to understand the distribution of velocities and the corresponding eigenvalue spectrum that a given collision sequence can produce. We formulate the problem for general N and state some basic theorems regarding the eigenvalues of the collision matrices and their products. The case of three beads of masses m1, m2, m3 is studied in detail. We exploit the fact that each collision sequence can be viewed as a billiard trajectory in a right triangle with non-standard reflection rules. Existence of families of periodic orbits are proven, and orbits that densely fill the triangle are computed. Eigenvalue distributions and position and velocity histograms are computed as a function of the restitution coefficient, both periodic and dense collision sequences are discussed, and a series of conjectures based on computational evidence are formulated. Comparisons are made between the eigenvalue distributions and autocorrelation matrices associated with dense trajectories generated from a chaotic collision sequence and spectra from matrix sequences generated from random orderings, and we describe how the three-bead system could be used as the basis for a random number generating algorithm that is computationally efficient. |
On the Occurrence of Superlinear Convergence of Exact and Inexact Krylov Subspace Methods
| Pengarang | : | Valeria Simoncini |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 247-272 |
| Abstrak | : | Krylov subspace methods often exhibit superlinear convergence. We present a general analytic model which describes this superlinear convergence, when it occurs. We take an invariant subspace approach, so that our results apply also to inexact methods, and to nondiagonalizable matrices. Thus, we provide a unified treatment of the superlinear convergence of GMRES, conjugate gradients, block versions of these, and inexact subspace methods. Numerical experiments illustrate the bounds obtained. |
Propagation, Observation, and Control of Waves Approximated by Finite Difference Methods
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 2) |
| Halaman | : | 197-243 |
| Abstrak | : | This paper surveys several topics related to the observation and control of wave propagation phenomena modeled by finite difference methods. The main focus is on the property of observability, corresponding to the question of whether the total energy of solutions can be estimated from partial measurements on a subregion of the domain or boundary. The mathematically equivalent property of controllability corresponds to the question of whether wave propagation behavior can be controlled using forcing terms on that subregion, as is often desired in engineering applications. Observability/controllability of the continuous wave equation is well understood for the scalar linear constant coefficient case that is the focus of this paper. However, when the wave equation is discretized by finite difference methods, the control for the discretized model does not necessarily yield a good approximation to the control for the original continuous problem. In other words, the classical convergence (consistency + stability) property of a numerical scheme does not suffice to guarantee its suitability for providing good approximations to the controls that might be needed in applications. Observability/controllability may be lost under numerical discretization as the mesh size tends to zero due to the existence of high-frequency spurious solutions for which the group velocity vanishes. This phenomenon is analyzed and several remedies are suggested, including filtering, Tychonoff regularization, multigrid methods, and mixed finite element methods. We also briefly discuss these issues for the heat, beam, and Schrödinger equations to illustrate that diffusive and dispersive effects may help to retain the observability/controllability properties at the discrete level. We conclude with a list of open problems and future subjects for research. |