| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 4) |
| Nomor Halaman | : | 709-721 |
| Abstraksi Narasi | : | We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts. Maximizing the long-term average throughput of parts is an important problem in both theory and practice. We define an appropriate state space required to analyze this problem and show that cyclic schedules which repeat a fixed sequence of robot moves indefinitely are the only ones that need to be considered. For the different classes of robotic cells studied in the literature, we discuss the current state of knowledge with respect to cyclic schedules. Finally, we discuss the importance of two fundamental open problems concerning optimal cyclic schedules, special cases for which these problems have been solved, and attempts to solve the general case. |
| Nama Pengarang | : | Assefaw Hadish Gebremedhin |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 4) |
| Nomor Halaman | : | 629-705 |
| Abstraksi Narasi | : | Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 553-575 |
| Abstraksi Narasi | : | The simplest problem with boundary layers, , is used to illustrate (i) why the perturbation series in powers of is asymptotic but divergent, (ii) why the optimally truncated expansion is "superasymptotic" in the sense that that error is proportional to , and (iii) how to obtain an improved "hyperasymptotic" approximation. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 519-549 |
| Abstraksi Narasi | : | The spring-loaded inverted pendulum (SLIP), or monopedal hopper, is an archetypal model for running in numerous animal species. Although locomotion is generally considered a complex task requiring sophisticated control strategies to account for coordination and stability, we show that stable gaits can be found in the SLIP with both linear and "air" springs, controlled by a simple fixed-leg reset policy. We first derive touchdown-to-touchdown Poincaré maps under the common assumption of negligible gravitational effects during the stance phase. We subsequently include and assess these effects and briefly consider coupling to pitching motions. We investigate the domains of attraction of symmetric periodic gaits and bifurcations from the branches of stable gaits in terms of nondimensional parameters. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 492-515 |
| Abstraksi Narasi | : | 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. |
| Nama Pengarang | : | Timo Betcke |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 469-491 |
| Abstraksi Narasi | : | 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. |
| Nama Pengarang | : | Per Edström |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 447-468 |
| Abstraksi Narasi | : | 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. |
| Nama Pengarang | : | Peter Lancaster |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 3) |
| Nomor Halaman | : | 407-443 |
| Abstraksi Narasi | : | 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. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 2) |
| Nomor Halaman | : | 349-365 |
| Abstraksi Narasi | : | 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 . |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 47 (No. 2) |
| Nomor Halaman | : | 317-346 |
| Abstraksi Narasi | : | 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. |