OPAC - Pencarian Artikel Jurnal & Majalah Library USD
Menampilkan semua artikel (Halaman 697 dari 34166, Total: 341652 data)
A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
klik untuk membaca file PDF
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 647-666 |
| Abstrak | : | 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. |
The Interplay of Ranks of Submatrices
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 637-646 |
| Abstrak | : | 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. |
A Survey of Public-Key Cryptosystems
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 4) |
| Halaman | : | 599-634 |
| Abstrak | : | We give an overview of the most important public-key cryptosystems and discuss the difficult task of evaluating the merit of such systems. |
Singular Value Decomposition, Eigenfaces, and 3D Reconstructions
| Pengarang | : | Neil Muller |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 518-545 |
| Abstrak | : | 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. |
Barycentric Lagrange Interpolation
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 501-517 |
| Abstrak | : | 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. |
Detecting an Inclusion in an Elastic Body by Boundary Measurements
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 477-498 |
| Abstrak | : | 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. |
Symplectic Rotational Geometry in Human Biomechanics
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 455-474 |
| Abstrak | : | In this paper we present rotational symplectic geometry for use in modern biomechanics of human motion. Generalized Hamiltonian formalism has been formulated on the configuration manifold consisting of rotational Lie groups. The proposed symplectic biodynamics includes conservative, dissipative, and driving forces and spinal reflex-like servo controls. Reduction of the angular configuration manifold enables topological brain-like control, as well as a subsequent topological analysis. |
Accelerating the Nonuniform Fast Fourier Transform
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 443-454 |
| Abstrak | : | The nonequispaced Fourier transform arises in a variety of application areas, from medical imaging to radio astronomy to the numerical solution of partial differential equations. In a typical problem, one is given an irregular sampling of N data in the frequency domain and one is interested in reconstructing the corresponding function in the physical domain. When the sampling is uniform, the fast Fourier transform (FFT) allows this calculation to be computed in operations rather than operations. Unfortunately, when the sampling is nonuniform, the FFT does not apply. Over the last few years, a number of algorithms have been developed to overcome this limitation and are often referred to as {\em nonuniform FFTs} (NUFFTs). These rely on a mixture of interpolation and the judicious use of the FFT on an oversampled grid [A. Dutt and V. Rokhlin, {\em SIAM J.\ Sci.\ Comput.}, 14 (1993), pp. 1368--1383].\ \indent% In this paper, we observe that one of the standard interpolation or ``gridding" schemes, based on Gaussians, can be accelerated by a significant factor without precomputation and storage of the interpolation weights. This is of particular value in two- and three-dimensional settings, saving either in storage in d dimensions or a factor of about 5--10 in CPU time (independent of dimension). |
Single Transferable Votes with Tax Cuts
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 417-442 |
| Abstrak | : | Some tally methods for preferential elections are discussed from the following point of view: How well do they respect a wish from the voter that subsidiary votes in the ballot cannot hurt the chances of the ballot's top-ranked candidate? The standard variation of single transferable votes (STV) is constructed to obey this principle, but other defects show up, in particular nonmonotonicity, premature eliminations, and free rides. The tax cut algorithm is also an essential part of Meek's modification of STV. Properties of the algorithm are established and other ways to apply it are considered, with the purpose of reducing the election method's weaknesses without losing too many of its strengths. |
The Theory of Implementation of Social Choice Rules
| Pengarang | : | - |
| Nama Majalah/Jurnal | : | Siam Review |
| Volume / Edisi | : | 46 (No. 3) |
| Halaman | : | 377-414 |
| Abstrak | : | Suppose that the goals of a society can be summarized in a social choice rule, i.e., a mapping from relevant underlying parameters to final outcomes. Typically, the underlying parameters (e.g., individual preferences) are unknown to the public authority. The implementation problem is then formulated: Under what circumstances canone design a mechanism so that the unknown information is truthfully elicited and the social optimum ends up being implemented? In designing such a mechanism, appropriate incentives must be given to the agents so that they do not wish to misrepresent their information. The theory of implementation or mechanism design formalizes this ``social engineering' problem and provides answers to the question just posed. I survey the theory of implementation in this article, emphasizing the results under two different benchmarks (that agents have dominant strategies and that they play a Nash equilibrium). Examples discussed include voting, and the allocation of private and public goods under complete and incomplete information. |