Sharedwww / msri07 / abstracts.texOpen in CoCalc
Author: William A. Stein
1
2\documentclass{article}
3\usepackage{url}
4\usepackage{fullpage}
5\title{Titles and Abstracts:\vspace{4ex}\mbox{}\\
6\Large Interactive Parallel Computation in Support of Research in\\Algebra, Geometry
7and Number Theory\vspace{4ex}\mbox{}\\
8\large A Workshop at MSRI Jan 29-Feb 2 organized by\\Burhanuddin, Demmel, Goins, Kaltofen, Perez, Stein, Verrill, and Weening}
9\begin{document}
10\maketitle
11\par\noindent
12{\large \bf Bailey: {\em\sf Experimental Mathematics and High-Performance Computing}}\vspace{1ex}\newline
13        {\em David Bailey  - Lawrence Berkeley Labs (LBL)}\vspace{1ex}\newline
14        \url{http://crd.lbl.gov/~dhbailey/}\vspace{1ex}\newline
15        {
16Recent developments in experimental mathematics'' have underscored the value of high-performance computing in modern mathematical research. The most frequent computations that arise here are high-precision (typically several-hundred-digit accuracy) evaluations of integrals and series, together with integer relation detections using the PSLQ'' algorithm. Some recent highlights in this arena include: (2) the discovery of BBP'-type formulas for various mathematical constants, including pi and log(2); (3) the discovery of analytic evaluations for several classes of multivariate zeta sums; (4) the discovery of Apery-like formulas for the Riemann zeta function at integer arguments; and (5) the discovery of analytic evaluations and linear relations among certain classes of definite integrals that arise in mathematical physics. The talk will include a live demo of the experimental mathematician's toolkit''.
17}\mbox{}\vspace{6ex}
18
19
20\par\noindent{\large \bf Bradshaw: {\em\sf Loosely Dependent Parallel Processes}}\vspace{1ex}\newline
21        {\em Robert Bradshaw  - University of Washington}\vspace{1ex}\newline
22        \url{robertwb@math.washington.edu}\vspace{1ex}\newline
23        {
24   Many parallel computational algorithms involve dividing the problem into several smaller tasks and running each task in isolation in parallel. Often these tasks are the same procedure over a set of varying parameters. Inter-process communication might not be needed, but the results of one task may influence what subsequent tasks need to be performed. I will discuss the concept of job generators, or custom-written tasks that generate other tasks and process their feedback. I would discuss this specifically in the context of integer factorization.
25   }\mbox{}\vspace{6ex}
26
27
28\par\noindent{\large \bf Cohn: {\em\sf Parallel Computation Tools for Research: A Wishlist}}\vspace{1ex}\newline
29        {\em Henry Cohn  - Microsoft Research}\vspace{1ex}\newline
30        \url{http://research.microsoft.com/~cohn/}\vspace{1ex}\newline
31        {}\mbox{}\vspace{6ex}
32
33
34\par\noindent{\large \bf Cooperman: {\em\sf Disk-Based Parallel Computing: A New Paradigm}}\vspace{1ex}\newline
35        {\em Gene Cooperman  - Northeastern University}\vspace{1ex}\newline
36        \url{http://www.ccs.neu.edu/home/gene/}\vspace{1ex}\newline
37        {
38   One observes that 100 local commodity disks of an array have approximately the same streaming bandwidth as a single RAM subsystem. Hence, it is proposed to treat a cluster as if it were a single computer with tens of terabytes of data, and with RAM serving as cache for disk.  This makes feasible the solution of truly large problems that are currently space-limited.  We also briefly summarize other recent activities of our working group: lessons from supporting ParGAP and ParGCL; progress toward showing that 20 moves suffice to solve Rubik's cube; lessons about marshalling from support of ParGeant4 (parallelization of a million-line program at CERN); and experiences at the SCIEnce workshop (symbolic-computing.org), part of a 5-year, 3.2 million euro, European Union project.  Our new distributed checkpointing package now provides a distributed analog of a SAVE-WORKSPACE command, for use in component-based symbolic software, such as SAGE.}\mbox{}\vspace{6ex}
39
40
41\par\noindent{\large \bf Edelman: {\em\sf Interactive Parallel Supercomputing: Today: MATLAB(r) and Python coming Cutting Edge: Symbolic Parallelism with  Mathematica(r) and MAPLE(r)}}\vspace{1ex}\newline
42        {\em Alan Edelman  - MIT}\vspace{1ex}\newline
43        \url{http://www-math.mit.edu/~edelman/}\vspace{1ex}\newline
44        {Star-P is a unique technology offered by Interactive Supercomputing after
45nurturing at MIT. Star-P through its abstractions is solving the ease of use
46problem that has plagued supercomputing. Some of the innovative features of
47Star-P are the ability to program in MATLAB, hook in task parallel codes
48written using a processor free abstraction, hook in existing parallel codes,
49and obtain the performance that represents the HPC promise. All this is
50through a client/server interface. Other clients such as Python or R could
51be possible. The MATLAB, Python, or R becomes the "browser." Parallel
52computing remains challenging, compared to serial coding but it is now that
53much easier compared to solutions such as MPI. Users of MPI can plug in
54their previously written codes and libraries and continue forward in Star-P.
55
56Numerical computing is challenging enough in a parallel environment,
57symbolic computing will require even more research and more challenging
58problems to be solved. In this talk we will demonstrate the possibilities
59and the pitfalls.
60}\mbox{}\vspace{6ex}
61
62
63\par\noindent{\large \bf Granger: {\em\sf Interactive Parallel Computing using Python and IPython}}\vspace{1ex}\newline
64        {\em Brian Granger  - Tech X Corp.}\vspace{1ex}\newline
65        \url{http://txcorp.com}\vspace{1ex}\newline
66        {
67Interactive computing environments, such as Matlab, IDL and
68Mathematica are popular among researchers because their
69interactive nature is well matched to the exploratory nature of
70research.  However, these systems have one critical weakness:
71they are not designed to take advantage of parallel computing
72hardware such as multi-core CPUs, clusters and supercomputers.
73Thus, researchers usually turn to non-interactive compiled
74languages, such as C/C++/Fortran when parallelism is needed.
75
76In this talk I will describe recent work on the IPython project
77to implement a software architecture that allows parallel
78applications to be developed, debugged, tested, executed and
79monitored in a fully interactive manner using the Python
80programming language.  This system is fully functional and allows
81many types of parallelism to be expressed, including message
82passing (using MPI), task farming, shared memory, and custom user
83defined approaches.  I will describe the architecture, provide an
84overview of its basic usage and then provide more sophisticated
85examples of how it can be used in the development of new parallel
86algorithms.  Because IPython is one of the components of the SAGE
87system, I will also discuss how IPython's parallel computing
88capabilities can be used in that context.
89    }\mbox{}\vspace{6ex}
90
91
92\par\noindent{\large \bf Harrison: {\em\sf Science at the petascale: tools in the tool box}}\vspace{1ex}\newline
93        {\em Robert Harrison  - Oak Ridge National Lab}\vspace{1ex}\newline
94        \url{http://www.csm.ornl.gov/ccsg/html/staff/harrison.html}\vspace{1ex}\newline
95        {
96Petascale computing will require coordinating the actions of 100,000+
97processors, and directing the flow of data between up to six levels
98of memory hierarchy and along channels that differ by over a factor of
99100 in bandwidth. Amdahl's law requires that petascale applications
100have less than 0.001% sequential or replicated work in order to
101be at least 50% efficient. These are profound challenges for all but
102the most regular or embarrassingly parallel applications, yet we also
103demand that not just bigger and better, but fundamentally new science.
104In this presentation I will discuss how we are attempting to confront
105simultaneously the complexities of petascale computation while
106increasing our scientific productivity. I hope that I can convince you
107that our development of MADNESS (multiresolution adaptive numerical
108scientific simulation) is not as crazy as it sounds.
109
110This work is funded by the U.S. Department of Energy, the division of
111Basic Energy Science, Office of Science, and was performed in part
112using resources of the National Center for Computational Sciences, both
113under contract DE-AC05-00OR22725 with Oak Ridge National Laboratory.
114    }\mbox{}\vspace{6ex}
115
116
117\par\noindent{\large \bf Hart: {\em\sf Parallel Computation in Number Theory}}\vspace{1ex}\newline
118        {\em Bill Hart  - Warwick}\vspace{1ex}\newline
119        \url{http://www.maths.warwick.ac.uk/~masfaw/}\vspace{1ex}\newline
120        {
121This talk will have two sections. The first will
122introduce a new library for number theory which is
123under development, called FLINT. I will discuss the
124various algorithms already available in FLINT, compare
125them with similar implementations available elsewhere,
126and speak about what the future holds for FLINT, with
127the focus on parallel processing and integration into
128Pari and the SAGE package.
129
130The second part of the talk will focus on low level
131implementation details of parallel algorithms in
132number theory. In particular I will discuss the design
133decisions that we have made so far in the FLINT
134library to facilitate multicore and multiprocessor
135platforms.
136
137If time permits, there will be a live demonstration.
138}\mbox{}\vspace{6ex}
139
140
141\par\noindent{\large \bf Hida: {\em\sf Moving Lapack and ScaLapack to Higher Precision without Too Much Work}}\vspace{1ex}\newline
142        {\em Yozo Hida  - UC Berkeley}\vspace{1ex}\newline
143        \url{http://www.cs.berkeley.edu/~yozo/}\vspace{1ex}\newline
144        {I will be discussing recent developments in Lapack and ScaLapack
145libraries, along with some recent work on incorporating higher
146precision into Lapack and ScaLapack.}\mbox{}\vspace{6ex}
147
148
149\par\noindent{\large \bf Khan: {\em\sf Game Theoretical Solutions for Data Replication in Distributed Computing Systems}}\vspace{1ex}\newline
150        {\em Samee Khan  - University of Texas, Arlington}\vspace{1ex}\newline
151        \url{sakhan@cse.uta.edu}\vspace{1ex}\newline
152        {
153Data replication is an essential technique employed to reduce the user
154perceived access time in distributed computing systems. One can find numerous
155algorithms that address the data replication problem (DRP) each contributing in
156its own way. These range from the traditional mathematical optimization
157techniques, such as, linear programming, dynamic programming, etc. to the
158biologically inspired meta-heuristics. We aim to introduce game theory as a new
159oracle to tackle the data replication problem. The beauty of the game theory
160lies in its flexibility and distributed architecture, which is well-suited to
161address the DRP. We will specifically use action theory (a special branch of
162game theory) to identify techniques that will effectively and efficiently solve
163the DRP. Game theory and its necessary properties are briefly introduced,
164followed by a through and detailed mapping of the possible game theoretical
165techniques and DRP. As an example, we derive a game theoretical algorithm for
166the DRP, and propose several extensions of it. An elaborate experimental setup
167is also detailed, where the derived algorithm is comprehensively evaluated
168against three conventional techniques, branch and bound, greedy and genetic
169algorithms.
170}\mbox{}\vspace{6ex}
171
172
173\par\noindent{\large \bf Kotsireas: {\em\sf Combinatorial Designs: constructions, algorithms and new results}}\vspace{1ex}\newline
174        {\em Ilias Kotsireas  - Laurier University, Canada}\vspace{1ex}\newline
175        \url{ikotsire@wlu.ca}\vspace{1ex}\newline
176        {
177We plan to describe recent progress in the search for combinatorial designs of
178high order. This progress has been achieved via some algorithmic concepts, such
179as the periodic autocorrelation function, the discrete Fourier transform and
180the power spectral density criterion, in conjunction with heuristic
181observations on plausible patterns for the locations of zero elements. The
182discovery of such patterns is done using meta-programming and automatic code
183generation (and perhaps very soon data mining algorithms) and reveals the
184remarkable phenomenon of crystalization, which does not yet possess a
185satisfactory explanation. The resulting algorithms are amenable to parallelism
186and we have implemented them on supercomputers, typically as implicit parallel
187algorithms.
188     }\mbox{}\vspace{6ex}
189
190
191\par\noindent{\large \bf Leykin: {\em\sf Parallel computation of Grobner bases in the Weyl algebra}}\vspace{1ex}\newline
192        {\em Anton Leykin  - IMA (Minessota)}\vspace{1ex}\newline
193        \url{leykin@ima.umn.edu}\vspace{1ex}\newline
194        {
195The usual machinery of Grobner bases can be applied to non-commutative algebras
196of the so-called solvable type. One of them, the Weyl algebra, plays the
197central role in the computations with $D$-modules. The practical complexity of
198the Grobner bases computation in the Weyl algebra is much higher than in the
199(commutative) polynomial rings, therefore, calling naturally for parallel
200computation.  We have developed an algorithm to perform such computation
201employing the master-slave paradigm. Our implementation, which has been carried
202out in C++ using MPI, draws ideas from both Buchberger algorithm and
203Faugere's $F_4$. It exhibits better speedups for the Weyl algebra in
204comparison to polynomial problems of the similar size.
205    }\mbox{}\vspace{6ex}
206
207
208\par\noindent{\large \bf Martin: {\em\sf MPMPLAPACK: The Massively Parallel Multi-Precision Linear Algebra Package}}\vspace{1ex}\newline
209        {\em Jason Martin  - James Madison University}\vspace{1ex}\newline
210        \url{http://www.math.jmu.edu/~martin/}\vspace{1ex}\newline
211        {
212For several decades, researchers in the applied fields have had access
213to powerful linear algebra packages designed to run on massively
214parallel systems.  Libraries such as ScaLAPACK and PLAPACK provide a
215rich set of functions (usually based on BLAS) for performing linear
216algebra over single or double precision real or complex data.
217However, such libraries are of limited use to researchers in discrete
218mathematics who often need to compute with multi-precision data types.
219
220This talk will cover a massively parallel multi-precision linear
221algebra package that I am attempting to write.  The goal of this C/MPI
222library is to provide drop-in parallel functionality to existing
223number theory and algebraic geometry programs (such as Pari, Sage, and
224Macaulay2) while preserving enough flexibility to eventually become a
225full multi-precision version of PLAPACK.  I will describe some
226architectural assumptions, design descisions, and benchmarks made so
227far and actively solicit input from the audience (I'll buy coffee for
228the person who suggests the best alternative to the current name).
229}\mbox{}\vspace{6ex}
230
231
232\par\noindent{\large \bf Moreno Maza: {\em\sf Component-level Parallelization of Triangular Decompositions}}\vspace{1ex}\newline
233        {\em Marc Moreno Maza  - Western Ontario}\vspace{1ex}\newline
234        \url{http://www.csd.uwo.ca/~moreno/}\vspace{1ex}\newline
235        {
236We discuss the parallelization of algorithms for solving polynomial systems symbolically by way of triangular decompositions. We introduce a component-level parallelism for which the number of processors in use depends on the geometry of the solution set of the input system. Our long term goal is to achieve an efficient multi-level parallelism: coarse grained (component) level for tasks computing geometric objects in the solution sets, and medium/fine grained level for polynomial arithmetic such as GCD/resultant computation within each task.
237
238Component-level parallelism belongs to the class of dynamic irregular parallel applications, which leads us to address the following questions: How to discover and use geometrical information, at an early stage of the solving process, that would be favorable to component-level parallel execution and load balancing? How to use this level of parallel execution to effectively eliminate unnecessary computations? What implementation mechanisms are feasible?
239
240We report on the effectiveness of the approaches that we have applied, including modular methods'', solving by decreasing order of dimension'', task cost estimation for guided scheduling''. We have realized a preliminary implementation on a SMP using multiprocessed parallelism in Aldor and shared memory segments for data communication. Our experimentation shows promising speedups for some well-know problems. We expect that this speedup would add a multiple factor to the speedup of medium/fine grained level parallelization as parallel GCD/resultant computations.
241}\mbox{}\vspace{6ex}
242
243
244\par\noindent{\large \bf Noel: {\em\sf Structure and Representations of Real Reductive Lie Groups: A Computational Approach}}\vspace{1ex}\newline
245        {\em Alfred Noel  - UMass Boston / MIT}\vspace{1ex}\newline
246        \url{http://www.math.umb.edu/~anoel/}\vspace{1ex}\newline
247        {
248I work with David Vogan (MIT) on the Atlas of Lie Groups and Representations. This is a project to make available information about representations of semi-simple Lie groups over real and p-adic fields. Of particular importance is the problem of the unitary dual: classifying all of the irreducible unitary representations of a given Lie group.
249
250I will present some of the main ideas behind the current and very preliminary version of the software. I will provide some examples also. Currently, we are developing sequential algorithms that are implemented in C++. However, because of time and space complexity we are slowly moving in the direction of parallel computation. For example, David Vogan is experimenting with multi-threads in the K-L polynomials computation module.
251
252This talk is in memory of Fokko du Cloux, the French mathematician who, until a few months ago, was the lead developer. He died this past November.
253    }\mbox{}\vspace{6ex}
254
255
256\par\noindent{\large \bf Pernet: {\em\sf Parallelism perspectives for the LinBox library}}\vspace{1ex}\newline
257        {\em Clement Pernet  - University of Waterloo}\vspace{1ex}\newline
258        \url{cpernet@uwaterloo.ca}\vspace{1ex}\newline
259        {
260LinBox is a generic library for efficient linear algebra with blackbox
261or dense matrices over a finite field or Z. We first present a few
262notions of the sequential implementations of selected problems, such
263as the system resolution or multiple triangular system resolution, or
264the chinese remaindering algorithm.  Then we expose perspectives for
265incorporating parallelism in LinBox, including multi-prime lifting for
266system resolution over Q, or parallel chinese remaindering. This last
267problem raises the difficult problem of combining early termination
268and work-stealing techniques.
269}\mbox{}\vspace{6ex}
270
271
272\par\noindent{\large \bf Qiang: {\em\sf Distributed Computing using SAGE}}\vspace{1ex}\newline
273        {\em Yi Qiang  - University of Washington}\vspace{1ex}\newline
274        \url{http://www.yiqiang.net/}\vspace{1ex}\newline
275        {
276Distributed SAGE (DSAGE) is a distributed computing framework for
277SAGE which allows users to easily parallelize computations and
278interact with them in a fluid and natural way. This talk will be
279focused on the design and implementation of the distributed computing
280framework in SAGE.  I will describe the application of the
281distributed computing framework to several problems, including the
282problem of integer factorization and distributed ray tracing.
283Demonstrations of using Distributed SAGE to tackle both problems will
284be given plus information on how to parallelize your own problems.  I
285will also talk about design issues and considerations that have been
286resolved or are yet unresolved in implementing Distributed SAGE.
287}\mbox{}\vspace{6ex}
288
289
290\par\noindent{\large \bf Roch: {\em\sf Processor oblivious parallel algorithms with provable performances: applications}}\vspace{1ex}\newline
291        {\em Jean-Louis Roch  - ID-IMAG (France)}\vspace{1ex}\newline
292        \url{http://www-id.imag.fr/Laboratoire/Membres/Roch_Jean-Louis/perso.html}\vspace{1ex}\newline
293        {
294Based on a work-stealing schedule, the on-line coupling of two algorithms
295(one sequential; the other one recursive parallel and fine grain) enables
296the design of programs that scale with provable performances on various
297parallel architectures, from multi-core machines to heterogeneous grids,
298including processors with changing speeds. After presenting a generic scheme
299and framework, on top of the middleware KAAPI/Athapascan that efficiently
300supports work-stealing, we present practical applications such as: prefix
301computation, real time 3D-reconstruction, Chinese remainder modular lifting
302with early termination, data compression.
303}\mbox{}\vspace{6ex}
304
305
306\par\noindent{\large \bf Tonchev: {\em\sf Combinatorial designs and code synchronization}}\vspace{1ex}\newline
307        {\em Vladimir Tonchev  - Michigan Tech}\vspace{1ex}\newline
308        \url{tonchev@mtu.edu}\vspace{1ex}\newline
309        {
310Difference systems of sets are combinatorial designs that arise in connection
311with code synchronization.  Algebraic constructions based on cyclic difference
312sets and finite geometry and algorithms for finding optimal difference systems
313of sets are discussed.
314}\mbox{}\vspace{6ex}
315
316
317\par\noindent{\large \bf Verschelde: {\em\sf Parallel Homotopy Algorithms to Solve Polynomial Systems}}\vspace{1ex}\newline
318        {\em Jan Verschelde  - UIC}\vspace{1ex}\newline
319        \url{http://www.math.uic.edu/~jan/}\vspace{1ex}\newline
320        {
321A homotopy is a family of polynomial systems which defines a deformation
322from a system with known solutions to a system whose solutions are needed.
323Via dynamic load balancing we may distribute the solution paths so that a
324close to optimal speed up is achieved.  Polynomial systems -- such as the
3259-point problem in mechanical design leading to 286,720 paths -- whose
326solving required real supercomputers twenty years ago can now be handled
327by modest personal cluster computers, and soon by multicore multiprocessor
328workstations.  Larger polynomial systems however may lead to more
329numerical difficulties which may skew the timing results, so that
330attention must be given to quality up'' as well.  Modern homotopy methods
331consist of sequences of different families of polynomial systems so that
332not only the solution paths but also parametric polynomial systems must be
333exchanged frequently.
334}\mbox{}\vspace{6ex}
335
336
337\par\noindent{\large \bf Wolf: {\em\sf Parallel sparsening and simplification of systems of equations}}\vspace{1ex}\newline
338        {\em Thomas Wolf and Winfried Neun }\vspace{1ex}\newline
339        \url{twolf@brocku.ca neun@zib.de}\vspace{1ex}\newline
340        {
341In a Groebner Basis computation the guiding principle for pairing and
342reducing' equations is a total ordering of monomials or of derivatives for
343differential Groebner Bases. If reduction based on an ordering is replaced by
344reduction to minimize the number of terms of an equation through another
345equation then on the downside the resulting (shorter) system does depend on the
346order of pairing of equations for shortening but on the upside there are number
347of advantages that makes this procedure a perfect addition/companion to the
348Groebner Basis computation. Such features are:
349
350  \begin{itemize}\item In contrast to Groebner Basis computations, this algorithm is safe in the sense that it does not need any significant amount of memory, even not temporarily.
351  \item It is self-enforcing, i.e. the shorter equations become, the more useful for shortening other equations they potentially get.
352  \item Equations in a sparse system are less coupled and a cost effective elimination strategy (ordering) is much easier to spot (for humans and computers) than for a dense system.
353  \item Statistical tests show that the probability of random polynomials to factorize increases drastically the fewer terms a polynomial has.
354  \item By experience the shortening of partial differential equations increases their chance to become ordinary differential equations which are usually easier to solve explicitly.
355  \item The likelihood of shortenings to be possible is especially high for large overdetermined systems. This is because the number of pairings goes quadratically with the number of equations but for overdetermined systems, more equations does not automatically mean more unknowns to occur which potentially obstruct shortening by introducing terms that can not cancel.
356  \item The algorithm offers a fine grain parallelization in the computation to shorten one equation with another one and a coarse grain parallelization in that any pair of two equations of a larger system can be processed in parallel.  In the talk we will present the algorithm, show examples supporting the above statements and give a short demo.
357\end{itemize}}\mbox{}\vspace{6ex}
358
359
360\par\noindent{\large \bf Yelick: {\em\sf Programming Models for Parallel Computing}}\vspace{1ex}\newline
361        {\em Kathy Yelick  - UC Berkeley}\vspace{1ex}\newline
362        \url{http://www.cs.berkeley.edu/~yelick/}\vspace{1ex}\newline
363        {
364The introduction of multicore processors into mainstream computing is
365creating a revolution in software development.  While Moore's
366Law continues to hold, most of the increases in transistor density will be
367used for explicit, software-visible parallelism, rather than increasing
368clock rate. The major open question is how these machines will be
369programmed.
370In this talk I will give an overview of some of the hardware trends, and
371describe programming techniques using Partitioned Global Address Space
372(PGAS)
373languages.  PGAS languages have emerged as a viable alternative to message
374passing programming models for large-scale parallel machines and clusters.
375They also offer an alternative to shared memory programming models (such as
376threads and OpenMP) and the possibility of a single programming model that
377will work well across a wide range of shared and distributed memory
378platforms.
379PGAS languages provide a shared memory abstraction with support for locality
380through the user of distributed data types.  The three most mature PGAS
381languages (UPC, CAF and Titanium) offer a statically partitioned global
382address space with a static SPMD control model, while languages emerging
383from the DARPA HPCS program are more dynamic.  I will describe these
384languages as well as our experience using them in both numeric and
385symbolic applications.}\mbox{}\vspace{6ex}
386
387
388\par\noindent\end{document}
`