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.
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.
62731399
NAS parallel benchmark results
The NAS (Numerical Aerodynamic Simulation) parallel benchmarks have been developed at NASA Ames Research Center to study the performance of parallel supercomputer. The eight benchmark problems are specified in a 'pencil and paper' fashion. The performance results of various systems using the NAS parallel benchmarks are presented. These results represent the best results that have been reported to the authors for the specific systems listed. They represent implementation efforts performed by personnel in both the NAS Applied Research Branch of NASA Ames Research Center and in other organizations.<<ETX>>
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.
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.
9982978
General Polynomial Time Decomposition Algorithms
We present a general decomposition algorithm that is uniformly applicable to every (suitably normalized) instance of Convex Quadratic Optimization and efficiently approaches the optimal solution. The number of iterations required to be within e of optimality grows linearly with 1/e and quadratically with the number m of variables. The working set selection can be performed in polynomial time. If we restrict our considerations to instances of Convex Quadratic Optimization with at most k 0 equality constraints for some fixed constant k 0 plus some so-called box-constraints (conditions that hold for most variants of SVM-optimization), the working set is found in linear time. Our analysis builds on a generalization of the concept of rate certifying pairs that was introduced by Hush and Scovel. In order to extend their results to arbitrary instances of Convex Quadratic Optimization, we introduce the general notion of a rate certifying q-set. We improve on the results of Hush and Scovel [8] in several ways. First our result holds for Convex Quadratic Optimization whereas the results of Hush and Scovel are specialized to SVM-optimization. Second, we achieve a higher rate of convergence even for the special case of SVM-optimization (despite the generality of our approach). Third, our analysis is technically simpler.
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.
16243913
Experiments with a Heuristic Compiler
This report describes some experiments in constructing a compiler that makes use of heuristic problem~solving techniques such as those incorporated in the General Problem Solver (GPS) [1]. The experiments were aimed at the dual objectives of throwing light on some of the problems of constructing more powerful programming languages and compilers, and of testing whether the task of writing a computer program can be regarded as a "problem" in the sense in which that term is used in GPS. The present paper is concerned primarily with the second objective--with analyzing some of the problem-solving processes that are involved in writing computer programs. At the present stage of their development, no claims will be made for the heuristic programming procedures described here as practical approaches to the construction of compilers. Their interest lies in what they teach us about the nature of the programming task.
36481911
Retrospective on "Causality in Device Behavior"
I first encountered causality in the late 1940s, while seeking to formalize the concept of political power (causation of the behavior of one person by another). This concept turned out to be closely related to the concept of identification in simultaneous equation models, then being investigated by the Cowles Commission for Research in Economics. I published in 1952-54 several papers [ 13,14 ] introducing a definition of causal ordering and exploring both the mathematical properties and the underlying semantics of the formalism. When, years later, I read the early papers on qualitative reasoning in AI, it seemed to me that causal ordering, and related ideas for applying the method of comparative statics (with which I had also had experience in my work in economics) provided a more powerful method than those being proposed.
31930258
How Many Missing Answers Can Be Tolerated by Query Learners?
We consider the model of exact learning using an equivalence oracle and an incomplete membership oracle. In this model, a random subset of the learners membership queries is left unanswered. Our results are as follows. First, we analyze the obvious method for coping with missing answers: search exhaustively through all possible "answer patterns" associated with the unanswered queries. Thereafter, we present two specific concept classes that are efficiently learnable using an equivalence oracle and a (completely reliable) membership oracle, but are provably not polynomially learnable if the membership oracle becomes slightly incomplete. The first class will demonstrate that the aforementioned method of exhaustively searching through all possible answer patterns cannot be substantially improved in general (despite its apparent simplicity). The second class will demonstrate that the incomplete membership oracle can be rendered useless even if it leaves only a fraction 1/poly(n) of all queries unanswered. Finally, we present a learning algorithm for monotone DNF formulas that can cope with a relatively large fraction of missing answers (more than sixty percent), but is as efficient (in terms of run-time and number of queries) as the classical algorithm whose questions are always answered reliably.