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.
6270234
Spectral Relaxation for K-means Clustering
The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.
17421545
Recent trends in the marketplace of high performance computing
In this paper we analyze major recent trends and changes in the High Performance Computing (HPC) market place. The introduction of vector computers started the area of 'Supercomputing'. The initial success of vector computers in the seventies was driven by raw performance. Massive parallel systems (MPP) became successful in the early nineties due to their better price/performance ratios, which was enabled by the attack of the 'killer-micros'. The success of microprocessor based on the shared memory concept (referred to as symmetric multiprocessors (SMP)) even for the very high-end systems, was the basis for the emerging cluster concepts in the early 2000s. Within the first half of this decade clusters of PC's and workstations have become the prevalent architecture for many HPC application areas on all ranges of performance. However, the Earth Simulator vector system demonstrated that many scientific applications could benefit greatly from other computer architectures. At the same time there is renewed broad interest in the scientific HPC community for new hardware architectures and new programming paradigms. The IBM BlueGene/L system is one early example of a shifting design focus for large-scale system. The DARPA HPCS program has the declared goal of building a Petaflops computer system by the end of the decade using novel computer architectures.
9115069
Causality in Device Behavior
Abstract This paper shows how formal characterizations of causality and of the method of comparative statics, long used in econometrics, thermodynamics and other domains, can be applied to clarify and make rigorous the qualitative causal calculus recently proposed by de Kleer and Brown [2]. The formalization shows exactly what assumptions are required to carry out causal analysis of a system of interdependent variables in equilibrium and to propagate disturbances through such a system. The intuitive concepts of causality captured by de Kleer and Brown provide a rough approximation to the standard analytic techniques that are used in the treatment of simultaneous algebraic and differential equations.
29911339
Artificial Intelligence: An Empirical Science
My initial tasks in this paper are, first, to delimit the boundaries of artificial intelligence, then, to justify calling it a science: is AI science, or is it engineering, or some combination of these? After arguing that it is (at least) a science, I will consider how it is best pursued: in particular, the respective roles for experiment and theory in developing AI. I will rely more on history than on speculation, for our actual experience in advancing the field has much to tell us about how we can continue and accelerate that advance. Many of my examples will be drawn from work with which I have been associated, for I can speak with greater confidence about what motivated that work and its methods (and about its defects) than I can about the work of others. My goal, however, is not to give you a trip through history, but to make definite proposals for our future priorities, using history, where relevant, as evidence for my views.
5520100
The Theory of Problem Solving
It is now about fifteen years since the first computer programs were written and tested that used the method of heuristic search to solve problems. Dozens of such programs, some designed for specific task domains, others claiming various degrees of generality, have now been described in the literature, and many experiments with their performance have been reported and analysed. It is an appropriate time to ask what has been learned from these experiments about the general theory of problem solving, and to try to summarize the present state of that theory.
45719384
A Characterization of Strong Learnability in the Statistical Query Model
In this paper, we consider Kearns' [4] Statistical Query Model of learning. It is well known [3] that the number of statistical queries, needed for "weakly learning" an unknown target concept (i.e. for gaining significant advantage over random guessing) is polynomially related to the so-called Statistical Query dimension of the concept class. In this paper, we provide a similar characterization for "strong learning" where the learners final hypothesis is required to approximate the unknown target concept up to a small rate of misclassification. The quantity that characterizes strong learnability in the Statistical Query model is a surprisingly close relative of (though not identical to) the Statistical Query dimension. For the purpose of proving the main result, we provide other characterizations of strong learnability which are given in terms of covering numbers and related notions. These results might find some interest in their own right. All characterizations are purely information-theoretical and ignore computational issues.
5542141
Applications of machine learning and rule induction
Machine learning is the study of computational methods for improving performance by mechanizing the acquisition of knowledge from experience. Expert performance requires much domain-specific knowledge, and knowledge engineering has produced hundreds of AI expert systems that are now used regularly in industry. Machine learning aims to provide increasing levels of automation in the knowledge engineering process, replacing much time-consuming human activity with automatic techniques that improve accuracy or efficiency by discovering and exploiting regularities in training data. The ultimate test of machine learning is its ability to produce systems that are used regularly in industry, education, and elsewhere.