OPAC - Pencarian Artikel Jurnal & Majalah Library USD
Menampilkan semua artikel (Halaman 696 dari 34166, Total: 341652 data)
A Survey of Eigenvector Methods for Web Information Retrieval
klik untuk membaca file PDF
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 135-161 |
| Abstrak | : | Web information retrieval is significantly more challenging than traditional well-controlled, small document collection information retrieval. One main difference between traditional information retrieval and Web information retrieval is the Web's hyperlink structure. This structure has been exploited by several of today's leading Web search engines, particularly Google and Teoma. In this survey paper, we focus on Web information retrieval methods that use eigenvector computations, presenting the three popular methods of HITS, PageRank, and SALSA. |
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 99-131 |
| Abstrak | : | Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom). |
A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 67-95 |
| Abstrak | : | A new method is presented for distributing data in sparse matrix-vector multiplication. The method is two-dimensional, tries to minimize the true communication volume, and also tries to spread the computation and communication work evenly over the processors. The method starts with a recursive bipartitioning of the sparse matrix, each time splitting a rectangular matrix into two parts with a nearly equal number of nonzeros. The communication volume caused by the split is minimized. After the matrix partitioning, the input and output vectors are partitioned with the objective of minimizing the maximum communication volume per processor. Experimental results of our implementation, Mondriaan, for a set of sparse test matrices show a reduction in communication volume compared to one-dimensional methods, and in general a good balance in the communication work. Experimental timings of an actual parallel sparse matrix-vector multiplication on an SGI Origin 3800 computer show that a sufficiently large reduction in communication volume leads to savings in execution time. |
On the Finite Element Solution of the Pure Neumann Problem
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 50-66 |
| Abstrak | : | This paper considers the finite element approximation and algebraic solution of the pure Neumann problem. Our goal is to present a concise variational framework for the finite element solution of the Neumann problem that focuses on the interplay between the algebraic and variational problems. While many of the results that stem from our analysis are known by some experts, they are seldom derived in a rigorous fashion and remain part of numerical folklore. As a result, this knowledge is not accessible (or appreciated) by many practitioners---both novices and experts---in one source. Our paper contributes a simple, yet insightful link between the continuous and algebraic variational forms that will prove useful. |
Bouncing Ball Modes and Quantum Chaos
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 43-49 |
| Abstrak | : | Quantum ergodicity for classically chaotic systems has been studied extensively both theoretically and experimentally in mathematics and physics. Despite this long tradition we are able to prove a new rigorous result using only elementary calculus. In the case of the famous Bunimovich stadium shown in Figure 1, we prove that the wave functions have to spread to any neighborhood of the wings. |
Product Eigenvalue Problems
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 47 (No. 1) |
| Halaman | : | 3-40 |
| Abstrak | : | Many eigenvalue problems are most naturally viewed as product eigenvalue problems. The eigenvalues of a matrix A are wanted, but A is not given explicitly. Instead it is presented as a product of several factors: . Usually more accurate results are obtained by working with the factors rather than forming A explicitly. For example, if we want eigenvalues/vectors of , it is better to work directly with B and not compute the product. The intent of this paperis to demonstrate that the product eigenvalue problem is a powerful unifying concept. Diverse examples of eigenvalue problems are discussed and formulated as product eigenvalue problems. For all but a couple of these examples it is shown that the standard algorithms for solving them are instances of a generic algorithm applied to a related cyclic matrix. |
Analysis Still Matters: A Surprising Instance of Failure of Runge--Kutta--Felberg ODE Solvers
| Pengarang | : | Joseph D. Skufca |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 729-737 |
| Abstrak | : | 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. |
Recovering Holomorphic Functions from Their Real or Imaginary Parts without the Cauchy--Riemann Equations
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 717-728 |
| Abstrak | : | 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. |
Low-Rank Solution of Lyapunov Equations
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 693-713 |
| Abstrak | : | 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. |
Fastest Mixing Markov Chain on a Graph
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 667-689 |
| Abstrak | : | 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. |