| Nama Pengarang | : | Joseph D. Skufca |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 729-737 |
| Abstraksi Narasi | : | This paper provides a nice example to illustrate that without supporting analysis, a numerical simulation may lead to incorrect conclusions. We explore a pedagogical example of failure of Runge--Kutta--Felberg (RKF) algorithms for a simple dynamical system that models the coupling of two oscillators. Although the system appears to be well-behaved, the explicit RKF solvers provide erratic numerical solutions. The mode of failure is based in a period-doubling route to chaos due to the existence of stable linear solutions in the problem. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 717-728 |
| Abstraksi Narasi | : | Students of elementary complex analysis usually begin by seeing the derivation of the Cauchy--Riemann equations. A topic of interest to both the development of the theory and its applications is the reconstruction of a holomorphic function from its real part, or the extraction of the imaginary part from the real part, or vice versa. Usually this takes place by solving the partial differential system embodied by the Cauchy--Riemann equations. Here I show in general how this may be accomplished by purely algebraic means. Several examples are given, for functions with increasing levels of complexity. The development of these ideas within the Mathematica software system is also presented. This approach could easily serve as an alternative in the early development of complex variable theory. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 693-713 |
| Abstraksi Narasi | : | This paper presents the Cholesky factor--alternating direction implicit (CF--ADI) algorithm, which generates a low-rank approximation to the solution X of the Lyapunov equation AX+XAT = -BBT. The coefficient matrix A is assumed to be large, and the rank of the right-hand side -BBT is assumed to be much smaller than the size of A. The CF--ADI algorithm requires only matrix-vector products and matrix-vector solves by shifts of A. Hence, it enables one to take advantage of any sparsity or structure in A. This paper also discusses the approximation of the dominant invariant subspace of the solution X. We characterize a group of spanning sets for the range of X. A connection is made between the approximation of the dominant invariant subspace of X and the generation of various low-order Krylov and rational Krylov subspaces. It is shown by numerical examples that the rational Krylov subspace generated by the CF--ADI algorithm, where the shifts are obtained as the solution of a rational minimax problem, often gives the best approximation to the dominant invariant subspace of X. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 667-689 |
| Abstraksi Narasi | : | We consider a symmetric random walk on a connected graph, where each edge is labeled with the probability of transition between the two adjacent vertices. The associated Markov chain has a uniform equilibrium distribution; the rate of convergence to this distribution, i.e., the mixing rate of the Markov chain, is determined by the second largest eigenvalue modulus (SLEM) of the transition probability matrix. In this paper we address the problem of assigning probabilities to the edges of the graph in such a way as to minimize the SLEM, i.e., the problem of finding the fastest mixing Markov chain on the graph. We show that this problem can be formulated as a convex optimization problem, which can in turn be expressed as a semidefinite program (SDP). This allows us to easily compute the (globally) fastest mixing Markov chain for any graph with a modest number of edges (say, ) using standard numerical methods for SDPs. Larger problems can be solved by exploiting various types of symmetry and structure in the problem, and far larger problems (say, 100,000 edges) can be solved using a subgradient method we describe. We compare the fastest mixing Markov chain to those obtained using two commonly used heuristics: the maximum-degree method, and the Metropolis--Hastings algorithm. For many of the examples considered, the fastest mixing Markov chain is substantially faster than those obtained using these heuristic methods. We derive the Lagrange dual of the fastest mixing Markov chain problem, which gives a sophisticated method for obtaining (arbitrarily good) bounds on the optimal mixing rate, as well as the optimality conditions. Finally, we describe various extensions of the method, including a solution of the problem of finding the fastest mixing reversible Markov chain, on a fixed graph, with a given equilibrium distribution. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 647-666 |
| Abstraksi Narasi | : | We introduce a concept of {similarity} between vertices of directed graphs. Let GA and GB betwo directed graphs with, respectively, nA and nB vertices. We define an nB \times nAsimilarity matrixS whose real entry sij expresses how similar vertex j (in GA ) is to vertex i (in GB ): we say that sij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of Sk +1 = BSkAT + BTSkA, where A and B are adjacency matrices of the graphs and S0 is a matrix whose entries are all equal to 1. In the special case where GA = GB = G, the matrix S is square and the score sij is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a nonnegative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 637-646 |
| Abstraksi Narasi | : | A banded invertible matrix T has a remarkable inverse. All "upper" and "lower" submatrices of T-1 have low rank (depending on the bandwidth in T). The exact rank condition is known, and it allows fast multiplication by full matrices that arise in the boundary element method. We look for the "right" proof of this property of T-1 . Ultimately it reduces to a fact that deserves to be better known: Complementary submatrices of any T and T-1 have the same nullity. The last figure in the paper (when T is tridiagonal) shows that, on and above the diagonal of T-1, all rows are proportional. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 4) |
| Nomor Halaman | : | 599-634 |
| Abstraksi Narasi | : | We give an overview of the most important public-key cryptosystems and discuss the difficult task of evaluating the merit of such systems. |
| Nama Pengarang | : | Neil Muller |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 3) |
| Nomor Halaman | : | 518-545 |
| Abstraksi Narasi | : | Singular value decomposition (SVD) is one of the most important and useful factorizations in linear algebra. We describe how SVD is applied to problems involving image processing---in particular, how SVD aids the calculation of so-called eigenfaces, which provide an efficient representation of facial images in face recognition. Although the eigenface technique was developed for ordinary grayscale images, the technique is not limited to these images. Imagine an image where the different shades of gray convey the physical three-dimensional structure of a face. Although the eigenface technique can again be applied, the problem is finding the three-dimensional image in the first place. We therefore also show how SVD can be used to reconstruct three-dimensional objects from a two-dimensional video stream. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 3) |
| Nomor Halaman | : | 501-517 |
| Abstraksi Narasi | : | Barycentric interpolation is a variant of Lagrange polynomial interpolation that is fast and stable. It deserves to be known as the standard method of polynomial interpolation. |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Nomor Edisi | : | 46 (No. 3) |
| Nomor Halaman | : | 477-498 |
| Abstraksi Narasi | : | We consider the problem of determining, within an elastic isotropic body , the possible presence of an inclusion D made of different elastic material {from} boundary measurements of traction and displacement. We prove that the volume (size) of D can be estimated, {from} above and below, by an easily expressed quantity related to work depending only on the boundary traction and displacement. |