15281282
Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
SUMMARY If problems involving unstructured meshes are to be solved efficiently on distributed-memory parallel computers, the meshes must be partitioned and distributed across processors in a way that balances the computational load and minimizes communication. The recursive spectral bisection method (RSB) has been shown to be very effective for such partitioning problems compared to alternative methods, but RSB in its simplest form is expensive. Here a multilevel version of RSB is introduced that attains about an order-of-magnitude improvement in run time on typical examples. 1. INTRODUCTION Unstructured meshes are used in several large-scale scientific and engineering problems, including finite-volume methods for computational fluid dynamics and finite-element methods for structural analysis. If unstructured problems such as these are to be solved on distributed-memory parallel computers, their data structures must be partitioned and distributed across processors; if they are to be solved efficiently, the partitioning must niaximize load balance and minimize interprocessor communication. Recently, the recursive spectral bisection method (RSB)[l] has been shown to be very effective for such partitioning problems compared to alternative methods. Unfortunately, RSB in its simplest form is expensive. We shall describe a multilevel version of RSB that attains about im order-of-magnitude improvement in run time on typical examples.
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.
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.
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.
145761361
CaMeRa: A computational model of multiple representations
This research aims to clarify, by constructing and testing a computer simulation, the use of multiple representations in problem solving, focusing on their role in visual reasoning. The model is motivated by extensive experimental evidence in the literature for the features it incorporates, but this article focuses on the system's structure. We illustrate the model's behavior by simulating the cognitive and perceptual processes of an economics expert as he teaches some well-learned economics principles while drawing a graph on a blackboard. Data in the experimental literature and concurrent verbal protocols were used to guide construction of a linked production system and parallel network, CaMeRa (Computation with Multiple Representations), that employs a “Mind's Eye” representation for pictorial information, consisting of a bitmap and associated node-link structures. Propositional list structures are used to represent verbal information and reasoning. Small individual pieces from the different representations are linked on a sequential and temporary basis to form a reasoning and inferencing chain, using visually encoded information recalled to the Mind's Eye from long-term memory and from cues recognized on an external display. CaMeRa, like the expert, uses the diagrammatic and verbal representations to complement one another, thus exploiting the unique advantages of each.
28048643
Generalization of an Elementary Perceiving and Memorizing Machine
The Elementary Perceiver and Memorizer (EPAM) is a context, and contains sufficient information to retrieve the model of human associative memory and the processes of image of the stimulus from the association memory when human verbal learning, written in the list-processing language necessary. IPL-V. A generalization of the EPAM model (called EPAM The complex image building processes also provide an assoIII), based on earlier experiments on EPAM 11, has been dative mechanism by means of which earlier learning can formulated and programmed. usefully be brought to bear on later learning. New stimuli arc In EPAM 111. stimulus configurations and their internal learned by associating together and modifying images of images are allowed indefinite complexity of sub-parts. Complex stimuli already learned. The model is an attempt to resolve internal images are built by associating together, in list structhe problem of how meaningful learning differs from nontures, tokens for retrieving information about the sub-parts meaningful learning, from the association memory. Empirical explorations of the model are concerned generally The concatenation of tokens by the image building process with variations in behaviour as a result of varying stimulus allows for the association of stimuli in many different contexts. and response meaningfulness. The token signifies the occurrence of a stimulus in a particular 3.ieM6HTapHan nporpaMMa jhh "H3yqaioinHx MauaeT coSbiTHe CTHMyjia b oco66hhom KOHTeKCTe, a npiiuihh" (3IIJIHM (EPAM)) npeacTaß^weTCH Moaejibio cyTCTByeT b aaHHOM naineKe aocTaToiHO HHdpopMauHH, accouHaTHßiioil nfiMfiTH h npoueccoß H3yiemm mob <rro6bi BooCpawenHe CTHMyjia moskho 6mjio Bbißec" y iciOBCKa; saiman Mo,Te.-ib narmcaHa b bh«6 si3uko, hs accouHaTHßHofl naMHTH b tom cnyqae, eoJiH sto A-1H pa3paf)OTKH CnHCKOB IPL 15. Ha OCHOBaHHH OKaHCeTCH Heo6xo«HMbiM. pe3y.ibTaTon Go.ice paiiHHx nonwTOK cihopMHyjinpoCjioiKHbie npoueccw, no3Bo^aiouiHe EPAM 111 CO3Ba.iacb ii cnporpaHMHpoßa,iacb ooo6meHHaH Moae^b naßaTb BoofipasKeHHH, Taicwe 3anaxaioT accoimaTHBEPAM jiß.inioumncHTaX Ha3bißaeMoft EPAM 111. Hiiit MexaHH3M, npn noMoiiw KOToporo npeAbiAymne B EPAM 111, mc.no noaiacTefl KOMiuieKCHbix <~thonuTH MoryT 3<h<beKTHßHbiM o6pa3oM BJiHHTb Ha cnemv.iob h BiiyTpeiiHHx hx n3oGpan<eHHH MomeT decayroiiuie. Hoßbie CTHMyjiu H3yiaioTCfl b pe3yjibTaTe npe.ie.-n.no yc.iovKHfiTbcu. OioiKHbie BiiyTpeHHHe accoiiHpoßaHHtf (tbm caMMM h Mo«H<bHKau.HH) HsyienH3oopn>KeHHn-iiMeiomHeMHoroypoßHeflHH(})opMauHH hux panbine BOo6pajKeHHft. MoaeJib npeacTaßJineT o no.tCTpyuTypectpohtch cnocoSoM accouHHpoßaHHH coCoft nonbrricy peuiHTb 3a«aqy o tom, KaKHM oopa3OM 3iia«iKon miMRKOB, npw noMomH kotopux cBe^eHHH pa3JinqaTb 3HaiaromHe CBeaenHH ot He3HaiaiomHx. o no.macTnx mo>kho BUBO«HTb H3 accouHaTHßHofl 3MnHpmiecKHe onwTbi npoßOflHmnecH Ha Mo^e^b, naMtiTii. Boo6me roßopn, hmciot c paaHUMH BH«aMH noße-3auen.ieHne iiaMeKOB npoueccoM co3«aHHH boosaeHHn, npoHCxofIHWHMH H3 pa3HOBHfIHOCTH 3HaienHfi pn>Kenmi no3Bo.ineT accou.HHpoßaTb cTHMy^u, npoHCTHMy^a h oTBeTa. cxoanmiio H3 Miioro pa3Hbix kohtckctob. HaMeK 03HaLa machine elementaire pour percevoir et mettre en mblir Information concernant les sous-parties, a partir de la moire (EPAM) est un modele de la memoire humaine d'assomemoire dissociation. ciation. et dcs process de la facon humaine d'apprendre L'enchainement dcs signes au moyen de l'image eUabor^e verbalement, 6crit en langage IPL-V. En partant dcs r«sulpermet d'associer dcs excitations dans un grand nombre de tnts de tests anteVieurs, on a dlabore' et programme" une contextes diffe>ents. Le signe montre qu'il existe une excitagcneralisation dv modele EPAM, appele EPAM 111. tion dans un contexte particulier et une information suffisante Sur EPAM 111, les configurations d'excitation et les images peut, grace ace signe, regene>er l'image de I'excitation a inteneures de ces configurations ont une complexitc indefinie partir de la memoire dissociation, quand cela est necessaire. de sous-parlies. Dcs images internes complexes sont dlaborees Les procedis complexes gui 61aborent l'image fournissent en groupant. en liste de structures, les signes destine* a retaaussi un m6canisme dissociation, permettant d'elaborer faci405 IX, 1] automata theory lement la toute premiere information a partir de la toute informations ayant un sens, de celles gui n'en ont pas. derniere. Les tests empiriques dv modele se rapportent gene>alement On decouvre de nouvelles excitations en groupant (et en aux variations de fonctionnement, celles-ci £tant le resultat modifiant) les images d'excitations deja connues. Cc modele d'excitations et de reponses variables. est un essai de r6soudre le probleme de la differentiation dcs
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.
21852626
Search and Reasoning in Problem Solving
In the course of the extensive research that has been done on problem solving in AI , several rather distinct ways have emerged for representing and thinking about problem solving tasks. One way to view problem solving is as search. We postulate some kind of space in which treasures are hidden. We build symbol structures (nodes) that model this space, and 'move ' operators that alter these symbol structures, taking us from one node to another. In this metaphor, solving a problem consists in searching the model of the space (selectively), moving from one node to another along links that connect them until a treasure is encountered. A second way of viewing problem solving is as reasoning. We postulate a system of logic that allows us to deduce new statements from axioms and previously deduced statements. We represent a problem by a set of axioms in the formal language of our logic. In this metaphor, solving the problem consists in accumulating more and more information (more and more statements) by inference until the answer to the problem has been found. A third way of viewing problem solving is as constraint satisfaction. We postulate a set of objects and various subsets defined by the constraints they satisfy. In this metaphor, solving a problem consists in narrowing down the original set to a subset or unique object that satisfies all of the constraints. In no sense are the metaphors mutually exclusive; metaphors seldom are. The same problem-solving algorithm can be viewed, now as search, now as reasoning, now as constraint satisfaction. Consider, for example, a simple theorem-proving program that works forward from a set of axioms, applying its rules of inference to these to obtain new expressions that can be added to the