6041481
Parallel preconditioning and approximation inverses on the Connection Machine
The authors present a new approach to preconditioning for very large, sparse, non-symmetric, linear systems. It explicitly computes an approximate inverse to the original matrix that can be applied most efficiently for iterative methods on massively parallel machines. The algorithm and its implementation on the Connection Machine CM-2 are discussed in detail and supported by timings obtained from real problem data.<<ETX>>
36271721
Industrial Application Areas of High-Performance Computing
In 1993, a list of the top 500 supercomputer sites worldwide was made available for the first time. Since then, the Top500 list has been published twice a year. The list allows a detailed and well-founded analysis of the state of high-performance computing (HPC). This article summarizes the recent trends in application areas of HPC systems, focusing on the increase in industrial installations and applications.
9150119
Thick-Restart Lanczos Method for Symmetric Eigenvalue Problems
This paper describes a restarted Lanczos algorithm that particularly suitable for implementation on distributed machines. The only communication operation is requires outside of the matrix-vector multiplication is a global sum. For most large eigenvalue problems, the global sum operation takes a small fraction of the total execution time. The majority of the computer is spent in the matrix-vector multiplication. Efficient parallel matrix-vector multiplication routines can be found in many parallel sparse matrix packages such as AZTEC [9], BLOCK-SOLVE [10], PETSc [3], P_SPARSLIB. For this reason, our main emphasis in this paper is to demonstrate the correctness and the effectiveness of the new algorithm.
38908855
Large-Scale SVD and Subspace-Based Methods for Information Retrieval
A theoretical foundation for latent semantic indexing (LSI) is proposed by adapting a model first used in array signal processing to the context of information retrieval using the concept of subspaces. It is shown that this subspace-based model coupled with minimal description length (MDL) principle leads to a statistical test to determine the dimensions of the latent-concept subspaces in LSI. The effect of weighting on the choice of the optimal dimensions of latent-concept subspaces is illustrated. It is also shown that the model imposes a so-called low-rank-plus-shift structure that is approximately satisfied by the cross-product of the term-document matrices. This structure can be exploited to give a more accurate updating scheme for LSI and to correct some of the misconception about the achievable retrieval accuracy in LSI updating. Variants of Lanczos algorithms are illustrated with numerical test results on Cray T3E using document collections generated from World Wide Web.
35264400
Parallel Efficiency of the Lanczos Method for Eigenvalue Problems
LBNL-42828 Parallel Efficiency of the Lanczos Method for Eigenvalue Problems ^ Kesheng Wu+and Horst Simon* Abstract Two of the commonly used versions of the Lanczos method for eigenvalues problems are the shift-and-invert Lanczos method and the restarted Lanczos method. In this talk, we will address two questions, is the shift-and-invert Lanczos method a viable option on massively parallel machines and which one is more appropriate for a given eigenvalue problem? Introduction T h i s talk is o n how to compute eigenvalues a n d eigenvectors of large sparse s y m m e t r i c matrices o n massively parallel machines. One of the the most c o m m o n l y used algorithms for this task is the Lanczos m e t h o d w h i c h projects the large eigenvalue p r o b l e m onto a low dimensional K r y l o v subspace [7, 10]. I n most cases, the K r y l o v subspace basis is built t h r o u g h a series of matrix-vector m u l t i p l i c a t i o n s , the whole Lanczos m e t h o d c a n be implemented w i t h a matrix-vector m u l t i p l i c a t i o n routine a n d a few simple vector operations. T h i s a l g o r i t h m is highly efficient on parallel machines a n d it is effective for c o m p u t i n g extreme a n d well separated eigenvalues. To compute the interior or not well-separated eigenvalues, the shift-and-invert Lanczos m e t h o d is one of the most effective methods. Since the eigenvalues of a m a t r i x A are related to the eigenvalues of (A — c r l ) by a simple relation X(A) = a + 1/X((A — c r l ) ) a n d the corresponding eigenvectors of A a n d (A — c r l ) are identical, the shift-and-invert scheme computes the extreme eigenvalues of (A — c r l ) a n d deduce the corresponding eigenvalues of A. W i t h appropriate choice of a, the extreme eigenvalues of (A — al)^ are well separated and can be easily computed. T h e shift-and-invert Lanczos m e t h o d needs to b u i l d a K r y l o v subspace basis of (A — c r l ) w h i c h is done by solving a series of linear systems involving the coefficient m a t r i x (A — a I). T h e linear systems need to be solved accurately a n d the only reliable means to accomplish this is by using a direct m e t h o d [5]. Because it is difficult to implement direct methods o n d i s t r i b u t e d parallel computers, efficient parallel i m p l e m e n t a t i o n has not been widely available u n t i l recently [1, 8]. T h i s talk w i l l present our s t u d y of the parallel efficiency of the shift-and-invert Lanczos m e t h o d using these newly available direct solvers. T h e study w i l l show that the shift-and-invert Lanczos m e t h o d is ' T h i s w o r k was s u p p o r t e d b y t h e D i r e c t o r , Office o f E n e r g y R e s e a r c h , Office o f L a b o r a t o r y P o l i c y a n d Infrastructure M a n a g e m e n t , of the U . S . D e p a r t m e n t of E n e r g y under C o n t r a c t N o . D E - A C 0 3 - 7 6 S F 0 0 0 9 8 . T h i s r e s e a r c h u s e d r e s o u r c e s o f t h e N a t i o n a l E n e r g y R e s e a r c h S c i e n t i f i c C o m p u t i n g C e n t e r , w h i c h is s u p p o r t e d b y t h e Office o f E n e r g y R e s e a r c h o f t h e U . S . D e p a r t m e n t o f E n e r g y . 'Lawrence Berkeley National Laboratory/NERSC, Berkeley, CA Email: {ksni, hdsimon}81bl.gov.
46294089
1992 Gordon Bell Prize Winners
16971158
Laboratory Replication of Scientific Discovery Processes
Fourteen subjects were tape-recorded while they undertook to find a law to summarize numerical doto they were given. The source of the data was not identified, nor were the variables lobeled semantically. Unknown to the subjects. the data were measurements of the distances of the planets from the sun and the periods of their revolutions obout it-equivalent to the doto used by Johonnes Kepler to discover his third low of planetary motion. Four of the 14 subjects discovered the some low as Kepler did (the period varies OS the 3/2 power of the distance), and a fifth come very close to the answer. The subiects’ protocols provide a detatled picture of the problem-solving searches they engoged in, which were mainly, but not exclusively, in the space of possible functions for fitting the data. and provide explanations OS to why some succeeded and the others foiled. The scorch heuristics used by the subjects ore similar to those embodied in the BACON program, a computer simulation of certain scientific discovery processes. The experiment demonstrates the feasibility of examining some of the processes of scientific discovery by recreating, in the laboratory, discovery situations of substontiol historical relevance. It demonstrates also. that under conditions rather similar to those of the originol discoverer, a low can be rediscovered by persons of ordinory intelligence (i.e., the intelligence needed for academic success in a good university). The data for the successful subjects reveal no “creative” processes in this kind of o discovery situation different from those that are regulorly observed in all kinds of problem-solving settings.
6977019
Rule Creation and Rule Learning Through Environmental Exploration
The task of learning from environment is specified. It requires the learner to infer the laws of the environment in terms of its percepts and actions, and use the laws to solve problems. Based on research on problem space creation and discrimination learning, this paper reports an approach in which exploration, rule creation and rule learning are coordinated in a single framework. With this approach, the system LIVE creates STRIPS-Iike rules by noticing the changes in the environment when actions are taken, and later refines the rules by explaining the failures of their predictions. Unlike many other learning systems, since LIVE treats learning and problem solving as interleaved activities, no training instance nor any concept hierarchy is necessary to start learning. Furthermore, the approach is capable of discovering hidden features from the environment when normal discrimination process fails to make any progress.
37804897
Directions for Qualitative Reasoning
Sacks & Doyle provide an excellent overview of the fundamental limitations of the SPQR representations for reasoning about the qualitative properties of dynamic systems. We take this opportunity to outline some new directions for qualitative reasoning. In this paper, we provide a rigorous mathematical characterization for the term “qualitative property” in the context of static and dynamic systems. Based on these characterizations, we show that interval representations are well suited for reasoning about the qualitative properties of static systems such as qualitative comparative statics and qualitative stability. Moreover, we also show that symbolic computations help in the derivation of useful global properties of dynamic systems which can be used to guide numerical sampling of differential equations. The integration of symbolic and numeric methods provides a powerful approach for automating the qualitative analysis of differential equations.
206581413
A Time for Talk and a Time for Silence
The computer stores mountains of information which it communicates worldwide through an enormous bandwidth. We must learn to exercise severe, intelligent selectivity in mining our data mountains, and to communicate information in ways that will inform and not bury the recipients.
206718678
A General Convergence Theorem for the Decomposition Method
The decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with support vector machines. Although there exist some versions of the method that are known to converge to an optimal solution, the general convergence properties of the method are not yet fully understood. In this paper, we present a variant of the decomposition method that basically converges for any convex quadratic optimization problem provided that the policy for working set selection satisfies three abstract conditions. We furthermore design a concrete policy that meets these requirements.