Accomplishments in Mathematics in High Performance Computing
ANNUAL PROGRAM ORGANIZERS
University of Bergen (Informatikk) was one of the main organizers
for the 1996-1997 annual program on "Mathematics in High
Performance Computing." He was also a co-organizer in the
IMA workshop on "Parallel Solution of Partial Differential
Equations," June 9-13, 1997. Below is is report:
brief note written 18 months after the conclusion of the IMA year
on HPC is intended to focus on some of the aspects and events
that took place. With the distance in time, one can judge the
impact and perhaps clearer see the many small factors that all
contribute to IMA being such a unique meeting place for applied
mathematics, each year setting an agenda, probing into a focused
area of importance to industry and society at large.
I had the great privilege to participate in the HPC year from
the early planning phase until its conclusion in the summer
of 97. This note is not intended to report on the complete year,
many events of considerable significance have been left out.
Rather, I will try to say just a few words about some of the
aspects that characterize IMA and that, in my opinion, contribute
to its unique atmosphere and stimulating environment.
year was carefully planned, starting almost two full years ahead
of time. An external committee of known experts with broad experience
from academia and industry was given responsibility. Several meetings
were conducted and guided by the IMA director workshops and specific
themes as well as tentative lists of invitees started to emerge.
It shall also be noted that it was properly recognized that
an upgrade of the IMA local computer facilities as well as the
local network would be required. Similarly, agreements on joint
sessions with the supercomputer center and proper access to
supercomputer cycles were made.
year was organized in three parts with a total of nine workshops.
A very large number of participants was invited. They represented
universities, research laboratories and industry, not only from
the US, but also a significant number of applied mathematicians
Each workshop was still small enough to foster a free flowing
exchange of ideas, a typical size being about 30 people. The
format is right, clearly derived from years of experience at
part should not be underestimated. The IMA staff is professional.
Every little detail to make visitors feel comfortable is attended
to. A welcome letter, efficient setup of keys and computer accounts
before arrival, help with housing etc. Anybody trying this without
similar experience knows how easily such matters can distract
attention. When many stays last from 5 to 10 days, the IMA makes
a big win by not wasting visitor time at all.
will limit this note to say a few words about the last tutorial
on software for PDEs. Half a dozen of the worlds best software
packages and their authors were invited to present and talk about
their software. Practical computer demonstrations were mandatory.
In fact, the entire tutorial (lasting a full week) was mainly
based on using WEB technology for presentation, talks and demos.
People had hands on exercises and the tutorial quickly turned
into a large software laboratory where authors tried each others
problems etc. In fact, the week can be characterized as a hybrid
between a tutorial (mainly targeting the post doctoral program)
and a workshop. Everybody worked hard, everybody learned something
and we all came away feeling that we had a fun week.
year had nine post doctor positions, some from the IMA industrial
programme, the rest directly under the HPC year. In addition,
I had some of my own Ph.D. students as well as a couple of postdocs
visiting from Europe for shorter periods of time. Today, 18 months
later I still correspond with about half of the postdocs from
time to time. They are now scattered around the US and in Europe,
in universities but also working for industry.
amount of science, say in the form of publications produced as
a direct result from the interactions at the IMA is hard to measure
due to the considerable time lag that always will occur. An example
should suffice: My student Talal Rahman met Xiaobing Feng from
Tennessee, several papers have been written and they still work
closely together. An example (among many) of how the IMA makes
people meet and mix, new ideas result and new long term scientific
collaborations are started.
Life after the IMA year
of the IMA visitors and participants return home with new friends
and contacts. A considerable subset met again in the spring of
1998 at the Mittag Leffler Institute in Stockholm, Sweden. Then
partly again at the Oberwolfach institute in Germany. There is
no doubt that most visitors remember their stay at the IMA as
a very stimulating time where new ideas came about and lifelong
scientific relationships got started.
from the University of Minnesota, School of Mathematics was
one of the organizers for the year on "Mathematics in High Performance
Computing." He was also one of the organizers for the April
28-May 2, 1997 workshop on "Grid Generation and Adaptive Algorithms."
and the June 9-13, 1997 workshop on "Parallel Solution of PDE."
During the academic year 1996-97, I was an organizer for the
IMA program on High Performance Computing. I also was an organizer
for two workshops; Grid Generation and Adaptive Algorithms,
April 28-May 2, 1997, and Parallel Solution of PDE, June 9-13,
1997. In addition, I organized the weekly Numerical Analysis
Seminar in which many of the IMA visitors participated.
I was involved in continuous informal interactions with the
IMA visitors. Several of the IMA post-docs worked on research
projects that followed my research program in microstructure
which will be described below. Matthias Gobbert and Andreas
Prohl developed and analyzed a discontinuous finite element
for microstructure computations, and Martin Kruzik worked on
a project to compute microstructure by relaxation.
Advances in the understanding of material microstructure are
playing an important role in the development of active materials:
shape memory, magnetostrictive, and ferroelectric materials.
During the past several years computational methods for the
equilibria of martensitic crystals based on elastic energy minimization
has been developed by Luskin in collaboration with students,
post-docs, and co-workers. The invariance of the energy density
with respect to symmetry-related states implies that the elastic
energy density is non-convex and must have multiple energy wells.
Microstructure then occurs as the fine-scale spatial oscillation
between these symmetry-related states to attain the lowest possible
energy state. During the 1996-97 IMA program on High Performance
Computing, Luskin developed and analyzed computational strategies
that cope with the complexity of microstructure in situations
that were formerly far beyond computational capability, and
he and his co-workers showed how these concepts apply also to
theories of micromagnetics and magnetostriction.
During the 1996-97 year, Luskin (jointly with Bo Li) considered
multi-well energy minimization problems modeling martensitic
crystals that can undergo either an orthorhombic to monoclinic
or a cubic to tetragonal transformation. They obtained results
for the approximation of a laminate with varying volume fractions.
They constructed energy minimizing sequences of deformations
which satisfy the corresponding boundary condition, and they
established a series of error bounds in terms of the elastic
energy for the approximation of the limiting macroscopic deformation
and the simply laminated microstructure. Finally, they gave
results for the corresponding finite element approximation of
the laminate with varying volume fractions.
In another project, Luskin (with Li and Riordan) analyzed a
class of piecewise linear, nonconforming finite element approximations
of a simply laminated microstructure which minimizes the nonconvex
variational problem for the deformation of martensitic crystals
which can undergo either an orthorhombic to monoclinic (double
well) or a cubic to tetragonal (triple well) transformation.
Discontinuous, nonconforming elements are appealing for problems
with microstructure because the admissible deformations have
more flexibility to approximate oscillatory functions. This
project extended the stability analysis and numerical analysis
to a class of nonconforming elements that have been used successfully
to compute microstructure.
The IMA program on the Mathematics of High Performance Computing
got off to an active and hand-on start with tutorials on The
Message Passing Interface Standard (MPI) on September 9--11,
1996 and High-Performance Fortran (HPF), September 11--13, 1996.
MPI and HPF are software tools which enable parallel computing.
The IMA was fortunate to have some of the developers of these
tools present the tutorial (Gropp and Lusk for MPI and Koelbel
and Schreiber for HPF). The post-docs were active participants
in the tutorial and several utilized these tools extensively
in their research.
In addition to the workshops, the post-docs and visitors were
actively involved in a weekly Post-Doc seminar (which was run
by the post-docs) and the weekly Numerical Analysis Seminar
which is run by the School of Mathematics in collaboration with
the IMA. Two of the program organizers (Bjørstad and
Luskin) were in residence during the entire year and ensured
continuity in organization.
Among the highlights of the program was the tutorial on PDE
Software held during April 21--25, 1997. This tutorial featured
presentations by eight leading developers of software for PDEs.
The presentations included an overview of the packages, a demonstration
of the software, carefully prepared exercises, and a general
discussion on the last day. The visitors and post-docs actively
learned to use the software on the prepared exercises, as well
as tried to utilize the software on problems of research interest.
The final day featured a stimulating and energetic discussion
among the developers and the participants on the different approaches
and future directions.
It was very exciting to see at this tutorial that many of the
concepts on adaptive error control, grid generation, and iterative
solvers that have been developed on a theoretical basis during
the past decade are now being used in general purpose software.
The following workshops on Grid Generation and Adaptive Algorithms,
April 28 -- May 2, 1997, and Parallel Solution of PDE, June
9--13, 1997, continued the discussion of grid generation, adaptive
methods, and iterative solvers and offered a view of future
directions for PDE software.
Many of the long-term visitors made significant contributions
to the post-doctoral program. Rolf Rannacher (in residence during
the spring program) gave a series of four of lectures on ``Computational
Methods for the incompressible Navier-Stokes Equations.'' the
numerical solution of the Navier-Stokes equations. Petter Bjørstad
assisted many of the visitors and post-docs in the development
of parallel versions of their codes. For instance, he guided
post-doctoral scientist Brian Suchomel in the development of
a parallel version of his code using MPI for message passing
and the additive Schwarz Domain Decomposition algorithm to solve
an elliptic pressure equation. Mitchell Luskin introduced several
post-docs (Gobbert and Kruzik) to computational problems in
The workshop on Grid Generation and Adaptive Algorithms during
April 28--May 2, 1997 was one of the two major workshops of
the Spring focus on Parallel Computational Mechanics. Grid generation
is a common feature of many computational tasks which require
the discretization and representation of space and surfaces.
The approximation of the equilibrium states and dynamics of
continua require that the continua be represented by a grid.
The workshop speakers discussed how the geometric complexity
of the physical object or the non-uniform nature of the solution
variable make an unstructured grid desirable. Since an efficient
grid requires knowledge of the computed solution, many of the
workshop speakers spoke on how to construct grids that are adaptively
computed with the solution.
Some of the themes discussed were the development of a posteriori
error estimators (Bank, Berzins, Dupont, Le Veque, Nochetto,
Rannacher, mesh generation schemes including refinement, coarsening,
and mesh movement (Bank, Bern, Mukherjee, applications to degenerate,
singular, or heterogeneous problems (Baker, Le Veque, Nochetto,
Oden, Shephard), and software (Bank, Le Veque).
Parallel computers are only easily programmed with regular data
structures, so the development of adaptive grid generation algorithms
which can utilize parallel computers effectively has posed a
great challenge. Approaches to repartioning and load balancing
were discussed by several workshop speakers (Biswas, Flaherty).
The workshop on Parallel Solution of PDE held during June 9--13,
1997, was the other major workshop of the program on Parallel
Computational Mechanics. Parallel computers offers the promise
of greatly increased performance and the routine calculation
of previously intractable problems. This period of concentration
and the workshop promoted the development and assessment of
new approximation and solution techniques which can take advantage
of parallel computers. Techniques discussed included domain
decomposition methods (Brenner, Cai, Chan, Dryja, Fischer, Hoppe,
Keyes, Pavarino, Widlund) and multigrid methods (Bastian, Rannacher,
Xu). Applications discussed included fluid dynamics, solid mechanics,
and semiconductor simulation).
Robert Schreiber from Hewlett-Packard,
Inc. (Hewlett-Packard Labs) was a member of the organizing committee
on "Mathematics in High Performance Computing." He also co-organized
the workshop on "Algorithms for Parallel Processing, September
16-20, 1996" along with the special IMA Short Course: High-Performance
Fortran (HPF) held on September 11-13, 1996.
He writes the following preface for the proceedings where he
is one of the editors:
The Workshop on Algorithms for Parallel Processing was held
at the IMA September 16 - 20, 1996; it was the first workshop
of the IMA year dedicated to the mathematics of high performance
computing. The workshop organizers were Abhiram Ranade of The
Indian Institute of Technology, Bombay, Michael Heath of the
University of Illinois, and Robert Schreiber of Hewlett Packard
Laboratories. Our idea was to bring together researchers who
do innovative, exciting, parallel algorithms research on a wide
range of topics, and by sharing insights, problems, tools, and
methods to learn something of value from one another. As the
remarkable ensemble of papers contained herein should show,
we seem to have succeeded in creating ample opportunity for
such exchanges. The papers offer a wide-ranging tour of recent
developments in the very rapidly growing and changing field
of parallel algorithms. They cover the following general areas:
models and mechanisms for parallel machines (Chapters 1-4),
discrete and combinatorial algorithms (Chapters 5-7),
mathematical issues in parallelizing compilers (Chapter 8),
parallel algorithms for matrix computation, differential equations,
random number generation, and Fourier methods (Chapters 9-14),
new parallel computer systems and software (Chapters 15-16).
hope that readers will find this collection as enjoyable and
informative as we have.
of the University of Maryland (Mathematics), Fletcher
Jones of (IBM (Research Division), and James
Turner of Rensselaer Polytechnic Institute (Computer
Science) have the following joint report:
Preparing for opportunities was the theme of a workshop on Minorities
and Applied Mathematics-Connections to Industry, held October
4-6, 1996 at the Institute for Mathematics and its Applications
(IMA), University of Minnesota.
Approximately sixty invited minorities in mathematical sciences
attended the workshop. Of these, forty were Ph.D. students from
mathematical sciences departments in North America; the other
twenty participants represented a range of professional experience
from postdoc to senior scientist. Also attending were Avner
Friedman, Director of the IMA; Robert Gulliver, Associate Director
of the IMA; and Barry Cipra, a science writer.
The workshop was arranged by the IMA Director and the organizers
to provide an atmosphere in which minority graduate students
could hear about the research and careers associated with applying
mathematics to real- world problems. The real-world problems
presented to students involved mathematics at all levels from
elementary to technical, and showed students the need to communicate
across disciplines with scientists and engineers having sophisticated
mathematical training. Students began that communication process
(listening and speaking) at this workshop. Their careers will
be enhanced by this type of exposure; they were encouraged to
seek similar opportunities at their home institutions and in
their home regions. Each graduate student attending the workshop
agreed to return to their home institution and make a presentation
about the workshop, so that its benefits would not be limited
to those who attended.
The composition of the workshop-- a relatively small group,
mostly graduate students-- was based on the model used at the
workshop for women at the IMA in February, 1996 and was intended
to create a comfortable and relaxed environment. The workshop
contained four components:
talks by senior participants about their technical work and
Technical talks about the applications of mathematics associated
with various real-world problems;
Focused small-group discussions charged to produce action
items for colleges and universities, government laboratories,
funding agencies and professional organizations;
An after-dinner talk by Earl Barnes of Georgia Tech describing
how the discovery of Karmarkar's algorithm affected IBM's
business strategy and the relationship between further developments
in the mathematics and changes in strategy by IBM and its
The minority mathematics community is small, and the workshop
was the first opportunity for many of the students to network
with minority professionals sharing their interest in mathematics.
The technical talks were uniformly of high quality, and covered
a range of applications, including manufacturing of semi-conductors,
microstructure of materials, design of a chemical vapor deposition
reactor, mathematical problems arising in biology including
freezing of tissues for biomedical engineering, dynamics of
proteins in aqueous solutions, transport of solutes across cell
membranes and reconstruction of images in tomography. The mathematics
involved included wavelets, Markov processes, optimization,
partial differential equations and computer models. (Abstracts
of all the talks are in Section IV below.)
The small-group discussion sessions were also modelled on the
program held for women in February. Each group included about
twelve people, typically eight graduate students and four senior
mathematicians. One or two people served as coordinators to
assure that everyone had a chance to speak and to assure that
the group covered all relevant topics. One person was designated
as recorder to prepare notes of each group's discussions. Another
member of each group was asked to present the group's recommendations
at the final assembly of all workshop participants. Student
volunteers introduced speakers after the morning session, providing
another chance for them to practice their communications skills.
The organizing committee was extremely pleased with the workshop.
Participants were so enthusiastic that one of their primary
suggestions was a request to meet again to see how people had
carried out the suggestions made to them. They wanted to use
another meeting to practice skills suggested at this workshop,
where graduate students would give more of the talks, and would
receive advance help in order to make maximum use of the conference.
The primary value of workshops like this is the students' exposure
to people like themselves with interests like theirs, who have
accomplished what they are striving to accomplish. All mathematicians
are members of many communities--minorities, women, men, analysts,
geometers, topologists, applied mathematicians. Workshops like
this do not substitute for the specialized meetings of those
communities; they serve to demonstrate the existence of a minority
mathematics community which is not visible to students isolated
in their graduate programs.
The meeting was valuable because minority mathematicians have
an unparalleled opportunity. Mathematics research and education
are rapidly changing. The minority mathematics community did
not prosper under the old model; there is a willingness in our
community to consider other models of preparation for a career
in research. This workshop showed that minority students are
eager to prepare themselves for twenty-first century opportunities.
Mathematical problems arising in industrial applications typically
embody complicated, interdisciplinary issues of formulation,
analysis and solution. Minorities in mathematical careers are
often attracted to areas in which their results can have a societal
impact. There are many opportunities provided by real-world
problems for high-quality research, contributions to practical
results, and rewarding scientific careers. The purpose of the
weekend workshop is to show examples of people and problems
from industrial settings and to develop a set of concrete action
items that individuals and agencies can carry out and help minority
scientists at all levels and in varied environments become involved
with industrial problems.
The first goal will be achieved through technical talks by selected
participants chosen based on their success with real-world problems.
The collection of action items will build on suggestions received
at earlier workshops.
Each breakout group was asked to discuss the following topics:
Undergraduate and graduate education in mathematical sciences
Transition from undergraduate to graduate work;
Preparing for opportunities
the gap between academia and industry;
of interdisciplinary work;
and the global economy.
Although each group took a slightly different perspective on
the main issues, many common elements were cited. Means of overcoming
difficulties faced by students at the transition points (undergraduate
to graduate, graduate to work) were subjects of numerous suggestions.
Since members of the minority community frequently work in isolation,
most of the recommendations were actions for individuals to
undertake to prepare themselves better. The key to increasing
the number of minority mathematicians is individual initiative
on the items discussed below.
The main recommendations from all breakout groups are listed
here in four groups; recommendations for faculty and students,
recommendations for students, recommendations for academic mathematical
sciences departments and recommendations for the professional
societies. (Some recommendations are listed under more than
Actions for everyone
Get connected; have and use e-mail and internet access
Make departmental presentations about this workshop; invite
students from other departments
Take advantage of computer center resources (C, C++, software
packages, LATEX, UNIX, EXCEL)
Encourage the Department to invite speakers who can give talks
about applications of mathematics (and to make contacts with
Attend seminars in other departments
Contribute information to Internet sites for minorities (information
about internships, co-ops, programs, etc.)
Become aware of other minority/professional organizations
Look for internships and summer appointments in industrial
Keep in contact with mentors
Set up a Web site on the Internet containing:
Profiles of minority industrial mathematicians
Names and research areas of minority graduate students
who are working toward the Ph. D. degree; thesis topics
Profiles of minority businesses
Listing of available internships
Profile of tools needed for successful graduate experience
(C, C++, Hypertext, GAMS, presentation skills, LATEX)
Profile of conference abstracts, speakers, e-mail addresses,
as in AARMS at http://www.wam.umd.edu/~rlj/aarms.html
; contribute to such sites
Information on how to subscribe to minority e-mail lists
Current sources of minority scholarships
List of industrial and academic mentors
Support for budding entrepreneurs, such as information
on how to get started, information about others interested
in starting businesses and information about writing proposals
and reviewing proposals
Information about getting involved with "virtual" companies
Use the Web to foster Applied Math team projects
Identify hot areas in applied mathematics
Encourage students to form teams around these areas
Support students planning and executing their chosen project
Encourage student presentations on their projects at conferences
Actions for students
Set a goal and remain focused on it
Spend some time learning how to learn mathematics; take responsibility
to prepare yourself
Explore academic offerings of other departments to broaden
research opportunities: take a computer course; perhaps minor
in some area of engineering, science, business, etc.
Develop facility with written/spoken language
Get computational experience; learn a computer language and
how to apply it to your problem
Request a cross-departmental math modeling class with strong
Start an interdisciplinary journal club (students getting
together to read articles from journals) or a graduate student
Get involved with a project involving applications or integrating
math with other disciplines
Make contact with other (minority) graduate students for possible
collaboration on research-seek out a "like-minded" group
Discuss with advisor "what lies ahead"
Always keep your resume in mind
Go to conferences (for example, SIAM conferences including
SIAM's Diversity Day during the SIAM meeting at Stanford,
July 14-18, 1997) and take a leadership role
Prepare for conferences by reading abstracts, deciding
on talks you will attend and contacting authors of articles
in which you are interested
Do things inside and outside of school to make yourself
When working on a project, always think about what part
or extensions will be publishable
an all-out effort before graduating and looking for a job
Network at every opportunity-- attend seminars, attend
conferences, e-mail authors of articles
Contact all your mentors and professors as you near completion
of your M.S. or Ph.D. degree, asking them to get the word
out that you are close to graduating
Ask professors and mentors to send recommendations; those
based on personal contact are particularly important
Send letters/resumes "out of cycle" when the majority
of letters/resumes are least likely to come (this is less
effective in academe than in industry)
Always follow up contacts
Continually update your resume
Stay aware of current events to facilitate conversations
during job interviews
Call ahead to determine which areas of research are of
interest to the company with which you are interviewing--
meet industry halfway by showing them you are a good match
with their needs
C. Actions for academic mathematical sciences departments
student-to-student forums conducted by graduate students for
undergraduate student math majors to talk about the transition
to graduate school
Have a "strategies to get a job" seminar (for undergraduates
and/or for graduate students). Invite employers of all types--
community colleges, four-year colleges, industry and government
Recognize and support students who plan to enter the job market
with a B.S. or a M.S. degree
Forward all job listings to all graduate students at all levels
a math modeling class where students can work on problems
from industry-- expose students to working in teams and learning
how to approach problems
Make the modeling class interdisciplinary by cross-listing
it with other departments
students who want to take courses outside the Mathematics
Invite speakers from industry to talk about real-world problems
Contact graduates who work in industry
Set up an Advisory Committee with invited representatives
from local industry to provide another source of speakers
Improve advising for graduate students; some groups even suggested
development and use of a placement exam
Offer support to students other than teaching assistantships;
research internships in industry would prepare students to
begin industrial careers as teaching assistantships encourage
them to pursue teaching
Be aware of students in other disciplines, such as EE, who
take lots of mathematics, as sources of double majors and
In industry, mathematics departments should explain their
usefulness to the company; in academe, mathematical sciences
departments should explain their usefulness to allied departments
Actions for professional societies
Encourage student participation at meetings
Organize events for students
Support students' attendance at society meetings (as is
done by the Society for Mathematical Biology)
from Tica Technologies, Inc. was one of the organizers for the
workshop on "Evolutionary Algorithms" held on October 21-25,
1996. He reports:
In my estimation, the 1996 workshop on "evolutionary algorithms"
yielded a number of important benefits. It brought together
representatives of the superconductor community, applied mathematics
community, and evolutionary algorithms community in a congenial
and constructive interchange. I believe a number of positive
results will follow from this. I describe several below.
Many of the interactions between representatives of different
fields are leading and will lead to beneficial results. For
example, some of the applied mathematicians became better acquainted
with techniques for using evolutionary algorithms for real-world
applications and intend to add the evolutionary techniques to
their problem-solving machinery. Several of the parallel computing
speakers discussed techniques for parallelizing algorithms at
a meta-level. (This approach is not one typically followed in
the evolutionary algorithm field, where hybridization of algorithms
tends to occur in the operator set.) The result of this is likely
to be renewed experimentation with hybridization techniques
in the evolutionary algorithm field. Finally, some of the insights
gained by members of the evolutionary algorithm field with regard
to minimizing evaluation time appeared to be of benefit to members
of the supercomputing field.
In addition, the workshop brought together representatives of
different branches of the evolutionary algorithm field. Again,
the result was a cross-fertilization of ideas that I expect
will result in applied and theoretical work for several years
The IMA did a wonderful job in creating the environment for
the workshop, in promoting it, and in structuring it so that
there was extensive time for offline interaction. I greatly
enjoyed attending the workshop, and benefited tremendously from
from the University of Tennessee (Computer Science) was one
of the organizers for the workshop on "Evolutionary Algorithms"
held on October 21-25, 1996. His report follows:
The Evolutionary Algorithms workshop assembled a variety of
people with differing viewpoints. The field is not mature, still
enjoying youthful exuberance (and occasional excesses). I believe
the workshop facilitated communication between many of the various
camps in the evolutionary computation field, encouraging mutual
cooperation, and challenging each to translate and integrate
within their own perspectives the principles and conceptions
of the others.
The workshop also provided opportunity for people who infrequently
have the opportunity to meet with each other - but who do belong
to the same subgroup of the field, and who do have similar outlooks
or techniques - to share and discuss ideas.
As for specific contributions made by myself or by by other
visitors to the IMA, I feel comfortable about commenting on
my own part.
My point of view is that it makes sense, within the vast collection
of evolutionary algorithms and variants, to focus attention
on a simple, commonly used type, to then formalize it as a mathematical
object, and to study it with the aim of proving theorems about
That puts me in the lunatic fringe of the Evolutionary Algorithms
crowd for various reasons ... not the least of which is that
the vast majority are interested in solving some specific problem
or class of problems (which are usually NP complete), and their
goal is to find a usable heuristic. Any heuristic - however
obtained - that seems to work, at least better than what was
tried before, is the answer; proof, to most, is at best an irrelevant
Although the paper I submitted for the IMA proceedings focuses
more on explaining the mathematical framework than anything
else, the message I tried to get across in my talk contained
the following basic ideas:
Standard GA theory, from the perspective of logical rigor,
leaves much to be desired.
There is an alternative, which, though more mathematically
demanding, has more solid foundations, more predictive power,
and is capable of supporting nontrivial and provably correct
That alternative points towards fixed points of an underlying
dynamical system, among other things, as important objects
in the theory.
Besides asymptotic results (i.e., proven theorems), there
is empirical evidence gathered from extensive computer runs
verifying the claim that the alternative theory can make qualitatively
correct assertions about the behavior of genetic search as
used in practice.
I hope you will be able to paraphrase parts of my comments to
serve your purposes. The workshop was quite enjoyable, and I
thought it a tremendous success. Best Regards.
of Colorado State University (Computer Science) was one of the
organizers for the October 21-25, 1996 workshop on "Evolutionary
Algorithms." He writes:
The support of the IMA for the Workshop on Evolutionary Algorithms
made it possible to bring together for the first time a significant
number of the top researchers working in the area of Evolutionary
Algorithms, including the fields of Genetic Algorithms, which
developed in the United States in the mid-70's, and Evolution
Strategies, which developed in Germany in the mid-70's. These
two communities worked in almost total isolation until 1990;
in the last 5 years or so the Evolution Strategies community
has been fairly active in integrating Genetic Algorithm based
concepts into their work. But knowledge of Evolution Strategies
on the part of the larger US community and even other European
communities has been slower to develop. By bringing together
key individuals in these communities in one place in a relative
small forum (50 individuals) commonalities and differences in
the two approaches were made much clearer. Even though I have
been one of perhaps a half dozen individuals in the Genetic
Algorithms community to interact with the Evolution Strategies
community since 1990, I learned new things at the workshop that
surprised me and deepen my understanding of the two approaches.
It is somewhat symbolic that the "Fathers" of these two fields,
John Holland and Hans Paul Schwefel, had only been briefly introduced
once before and were able to interact for the first time at
The workshop also did a great deal to clarify the current state
of the theory in Evolutionary Algorithms; the existing theory
might be characterized as belonging in at least two different
major camps. There is a high level macro-theory that looks at
the processing of "building blocks" and "schemata" that are
shared by many good solutions when searching a problem space.
There is also a low level micro-theory that builds exact Markov
models of the search process. The macro-level theory of course
ignores certain detail; the micro-level theory involves working
with detailed models that unfortunately growth exponentially
as a function of problem size. (The size of the models are larger
than the search space itself.) I think that the IMA workshop
helped both sides in this debate to present their cases and
to move toward common ground.
A concept that was discussed at the workshop includes the so-called
"No Free Lunch" result which shows that all search algorithms
are the same when their performance is averaged over all possible
discrete functions. Debate on this topic has motivated me to
do new theoretically work proving that there are interesting
and potentially useful ways to partition the set of all possible
discrete functions such that some search algorithms are indeed
better than others. The results in fact have practical implications
for problem representations and improving search methods.
Another area where there was some real progress was in the area
of communication between theorist and practitioners. A wide
range of applications were presented. In some cases, theoretically
motivated methods worked quite well. In other cases, practitioners
used ad hoc methods to obtain better performance than could
be achieved with theoretically motivated methods; but at least
some individuals on both sides went away with a better appreciation
of the successes and failures of current theory. I believe that
the workshop will help to change what practitioners say about
the current state of theory in the field.
Some very surprising and impressive applications were presented
at the workshop, including data decomposition, deriving control
parameters for modeling systems using partial differential equations
and even new best know solutions to bin packing problems.
Overall, I found the workshop not only useful for bring people
together and strengthening the community, but also as a learning
from the University of Maryland (Computer Science) was a member
of the organizing committee on "Mathematics in High Performance
Computing." She also co-organized the workshop on "The Mathematics
of Information Coding" held on November 11-15, 1996. She writes:
A workshop on Information Coding, Extraction, and Distribution
was held at IMA November 11-15. There were approximately 30
attendees. The speakers included Michael Orchard, Robert Gray,
Ahmed Tewfik, Jorma Rissanen, Julia Abrahams, Paul Siegel, Gil
Strang, Cynthia Dwork, George Cybenko, Chris Atkeson, Dianne
O'Leary, Geoff Davis, Eric Metois, Duncan Buell, and Manfred
Opper. Topics ranging from the mathematics of coding theory
to the practicalities of copyright preservation for Internet
resources drew spirited discussion and interaction among experts
in diverse but related fields. George Cybenko and Dianne O'Leary
made plans to collaborate on the study of iterative methods
for matrix approximation.
from New York University (Courant Institute, Mathematical Sciences
and Chemistry) is one of the organizers for the January 20-23
workshop on "Molecular Structure: Dynamics, Geometry, and Topology."
The workshop on macromolecular structure brought together, at
the heart of winter, applied mathematicians and biophysicists.
The talks covered many exciting current topics in molecular
mechanics, molecular dynamics, global minimization of potential
energy functions, fast electrostatics, parallelization of large-scale
molecular codes, and much more.
Most exciting about the workshop was the cross-fertilization
of ideas, as reflected by the many discussions throughout the
lectures and during the meals and long breaks. The mathematical
and biological scientists learned and exposed their colleagues
to new information, new ideas, and future challenges. We all
left the workshop feeling that the informal setting and small
group size really worked to make the conference what it should
be -- scientific exchanges of ideas -- rather than a continuous
series of expositions by people who had been on the lecture
circuit for a long time...
from the University California-San Diego (Computer Science and
Engineering) was one of the organizers for the March 12-13,
1997 workshop on "Structured Adaptive Mesh Refinement Grid Methods."
After the formal talks had ended, a number of us (SAMR workshop
participants) decided that there was enough interest to look
into building standardized software support for structured adaptive
mesh refinements. A web page will also be maintained.
from Tufts University (Mathematics) was one of the organizers
for the workshop on "Computational Radiology and Imaging: Therapy
and Diagnostics" held on March 17-21, 1997. He shares the following:
Margaret Cheney told Todd Quinto about a problem concerning
singularity detection from sonar data. Todd was able to solve
the problem, and even proposed a singularity detection algorithm
based on his solution.
Robert Levine learned about the ongoing work on diffusion tomography.
He talked to me about his interest in this subject, and I introduced
him to David Boas, a researcher in diffusion tomography at Tufts
University. Robert, David, Todd Quinto, and I have started a
working seminar on the subject together since then.
I can think of a lot of points and ideas and references that
I learned about at the workshop, or made other people aware
of, but that is too detailed for this report. Several participants
have made enthusiastic comments about the workshop.
Levine made me much more aware of the importance of the beam
selection (as opposed to beam weight optimization) problem
in radiation therapy planning.
I provided Meldon Lodwick with a list of references on biological
response models that have been proposed for the purpose of
formulating the radiation therapy planning problem as a constrained
I learned about various approaches to the diffusion tomography
problem: Michael Klibanov's and Simon Arridge's from their
talks, and Sarah Patch's through conversations with her.
I pointed out to Yair Censor that constraints used in the
radiation therapy planning problem often have strong "volume
dependence:" It may be acceptable to give a large dose to
a small piece of a healthy organ, but not to a large piece.
It is not immediately obvious how such constraints could be
incorporated into his approach to the radiation therapy planning
problem. He thought about it a bit and came up with a suggestion
that ought to be explored further.
I learned about some work by Lech Papiez on dose calculations
in radiation therapy planning, and gave him references to
the "Boltzmann/ Fokker-Planck splitting" method, which has
been proposed in the Nuclear Engineering literature and appears
to be closely related to Lech's ideas.
George Majda told me about his work on the Vlasov-Poisson
equation. Some aspects of this work appear related to the
dose calculation problem in radiation therapy planning. I
visited George at Ohio State University in early May, and
we discussed this subject further.
from the Universitaet Muenster (Fachbereich Mathematik) was
one of the organizers for the March 17-21, 1997 workshop on
"Computational Radiology and Imaging: Therapy and Diagnostics."
The meeting brought together specialists from quite different
fields. This resulted in many lively and often controversial
One example is regularization. While everybody agreed that some
kind of regularization is necessary for virtually all medical
imaging problems, some people contended that Tikhonov regularization
is not sufficient. It does not permit to take into account properly
the properties of the image/object to be reconstructed, nor
does it reflect the role of the observer. These questions led
to very lively discussions after the talks of Barrett, Herman
and Johnson. A related controversial issue was assessment of
image quality. Barrett and Herman pointed out quite clearly
that naive distortion measures for images, such as norms, are
insufficient. Statistical and psychological assessment methods
such as ROC studies are required.
Another subject which was discussed quite controversially was
the usefulness of seriously ill-posed problems in medical imaging,
such as impedance and near infrared imaging. Some participants
frankly questioned the practical value of such techniques, describing
situations in which these methods are bound to fail. On the
other hand, Arridge presented simulations and also reconstructions
of measured data which demonstrate that near infrared imaging
can produce useful pictures for neonatal heads. Isaacson impressed
the audience with quite realistic patient studies. His talk
demonstrated the potential and the limitations of imaging techniques
based on seriously ill-posed problems.
A criticism which often came up was oversimplification and naive
modeling, in particular in connection with ultrasonic and optical
imaging. The modeling of noise and its propagation through the
algorithm has almost never been discussed.
Jaeger stressed in his talk that image reconstruction and image
enhancement should be considered as a single task. An example
is the removal of artifacts from CT pictures which should be
done on the data rather than on the image.
Sparr brought up Doppler imaging and the relevant mathematical
apparatus which has been developed recently by Sharafutdinov.
This talk impressively demonstrated how new mathematics leads
to new imaging techniques. The role of mathematics in 3D imaging
was the theme of the talk of Clack. A few years ago the underlying
mathematics was understandable only to a few experts, but it
is now almost as simple and elegant as in the 2D case. However,
there is still need for algorithms which can handle the case
of truncated projections.
Several approaches to the radiation treatment planning problem
were discussed in the talks by Censor, Levine, and Lodwick.
Levine stressed the importance of selecting a clinically manageable
number of beams, an aspect of the treatment planning problem
that is neglected in algorithms for optimizing the weights of
One of the mathematical tools which came up in many talks was
the transport equation. It serves as a model for different modalities
such as treatment planning, optical imaging, tomography including
scatter, and emission tomography. It seems that a large part
of medical imaging can be viewed as inverse problems for the
was one of the organizers of the April 7-11, 1997 workshop on
Mathematical and Computational Issues in Drug Design. Following
is the panel discussion where he served as moderator:
DISCUSSION: NEW PROBLEMS THAT SHOULD BE ADDRESSED IN THE NEXT
PANELISTS: GORDON CRIPPEN, SIMON KEARSLEY, GARLAND MARSHALL
and PHIL PORTOGHESE
This panel's challenge was to identify important problems and
challenges in drug discovery that should be addressed within
the next decade given steady, predictable improvement in computational
power and perhaps less predictable improvement in algorithms
and methods. What are the pressing problems and bottlenecks
that may succumb to new computational and theoretical approaches?
Garland Marshall discussed the need for improved methods to
deal with error analysis and propagation of errors in the drug
discovery and optimization process. We routinely face many sources
of error, experimental and theoretical, that complicate our
efforts to interpret and predict structure-activity relationships.
He also noted that we need to improve our ability to predict
the structure of drug receptors. Despite the impressive increases
in the ability of Xray crystallography and NMR to solve the
structures of biologically relevant macromolecules, many critical
receptors remain intractable. For example, 7-helical transmembrane,
G protein-coupled receptors (7TM GPCRs) make up the largest
single class of receptor targeted by today's drugs, yet no experimental
structures are available due to the extreme difficulties in
crystallizing transmembrane proteins. He also noted the immense
informatics problem posed by the explosion of data available
on the internet. We're "drowning in a sea of data," with only
primitive tools to integrate, assimilate, and interpret the
data. The explosion of genomics data is only beginning, due
to the massive efforts behind the human genome project (the
goal is to completely sequence the 3 billion bases in human
DNA by 2005) and other sequencing efforts targeting a variety
of microorganisms and pathogens.
Phil Portoghese also discussed the importance of 7TM GPCRs,
noting that our only structural information comes from low-resolution
experimental data and approximate homology models. The mechanism
by which 7TM GPCRs transduce an extracellular signal across
the membrane is poorly understood. He described experimental
methods that can provide additional data to help modeling, such
as recent work in making chimeric receptors that combine features
of two different receptors in a single molecule. For example,
an extracellular loop of the kappa-opiate receptor was transferred
to the mu-opiate receptor, resulting in a new, kappa-selective,
chimeric receptor. Current structures and models are not able
to explain the difference between 7TM GPCR agonists (molecules
that turn on an intracellular response) and antagonists (molecules
that inhibit the intracellular response). For example, morphine-type
molecules containing an N-CH3 group are agonists
at the mu-opiate receptor, but converting the N-CH3
group to N-CH2-cyclopropyl produces an antagonist.
This is a very small structural change, yet it produces a dramatically
Gordon Crippen noted that structure-activity relationships and
computer-assisted drug design rely on the rather vague notion
of molecular similarity as a central theme: similar molecules
tend to have similar biological activity. However, we have many
different ways of defining, measuring, and calculating similarity.
He suggested that molecular similarity should be defined relative
to the environment in which it is being measured, rather than
as an independent property. He also addressed the critical problem
of modeling oral bioavailability and drug distribution within
the body. We have extremely limited control and understanding
of how to alter chemical structure to achieve the desired properties
(for example, a pill that is stable in the gut, reaches the
target organ and receptors intact, has a long enough half-life
to require only 1-2 doses per day, and does not produce toxic
metabolites). Drug design and discovery is a complex, interdisciplinary
problem: rather than focus on isolated problems, we should consider
the entire system as a large graph depicting how drugs interact
with the body. The nodes are organs, tissues, fluids, membranes,
and other structures within the body. The edges are known or
hypothetical pathways; sometimes there may be more than one
path between a pair of nodes. Nodes are labeled by various capacities,
edges by rates and permissions. Can we integrate known data
into such a model?
Simon Kearsley provided a brief historical overview and a map
to the future of modeling challenges, noting that modeling has
already had a large impact in lead identification and optimization.
Due to the advent of high-throughput screening, genomics, and
bioinformatics, data mining and modeling are being used to help
biologists get needed chemistry support (for example, by computationally
identifying existing molecules in databases that validate biological
hypotheses, which in turn creates demand for additional, optimized
molecules). Current approaches have focused on the early stages
of drug discovery by improving the odds through statistical
and qualitative methods, for example, by helping to prioritize
screening and assisting in the identification of new leads.
Such methods include two-dimensional chemical substructure and
similarity searching, and three-dimensional superposition and
docking calculations. He suggested that the next challenge is
in information science: extrapolating from data mining to "concept"
mining and mining relationships in the data, going beyond improving
the odds by studying case histories and anticipating decision
points. He also mentioned that modeling approaches will need
to head toward modeling cellular processes and relationships
(similar to Gordon Crippen's ideas). This will require a canonicalization
of text, and the building of regular vocabularies and thesauri
to deal with the huge number of imprecise names and synonyms
in biology. A formalized mathematical language will need to
be developed for biology which can deal with a limited number
of observable properties and data. He mentioned the need for
technology to deal with very large databases and "data warehousing":
for example, data integration, data "scrubbing," and multidimensional
trend analysis. He also discussed the need for rule-generating
algorithms that can deal with fuzzy logic and ambiguity. These
methods will need to define and measure information content,
including the subjectivity content, deal with noise and sparse
data, and capture human expertise and knowledge.
There are clearly huge problems, challenges, and opportunities
for drug discovery in the next decade. Most of today's methods
focus on the early phases of drug discovery, which consume only
a small fraction of the time and money (less than 20%) of the
total path (10-12 years, $300-500 million) on the way to a marketed
drug. Integrated approaches such as those suggested by Kearsley
and Crippen have the potential to improve drug discovery further
down the expensive and time-consuming development process, but
will require increasingly sophisticated computational methods
and information science technology.
W.J. Howe were co-organizers of the April 7-11,
1997 workshop on Mathematical and Computational Issues in Drug
Design. Following is the panel discussion where they served
DISCUSSION: IMPORTANT CURRENT PROBLEMS IN DRUG DESIGN THAT MAY
BE COMPUTATIONALLY TRACTABLE
PANELISTS: DAVE DOHERTY, BILL DUNN, GRAHAM and RICHARDS DOUG
The intent of the first panel discussion was to identify areas,
within the broad range of fields represented at the workshop,
in which there are particularly important problems that may
be amenable to theoretical, mathematical, or computational advancement.
The focus was on areas that are currently under study, as opposed
to the second panel discussion which covered areas that one
may anticipate will begin to yield to computational methods
within 5-10 years or so. Given the breadth of the subject matter
covered at the workshop, the issues presented during the panel
discussions were necessarily only a small subset of a potential
list of "important problems," and they were obviously biased
by the particular areas of research interest of the panelists.
Nonetheless, each of the issues presented by a panelist engendered
considerable discussion among the workshop participants, and
the issues discussed in the first panel session can be considered
to be representative of problems currently under study by numerous
scientists in the field.
The panel discussion was structured around brief presentations
by each of the panelists on one or more issues viewed as particularly
difficult or important for the furtherance of the field. Each
presentation was then followed by discussion among the larger
audience. After the four presentations were complete, additional
topics and issues were put forth for discussion by workshop
participants. Following is a brief summary of the issues presented
by the panelists and other participants.
The approach taken by Graham Richards was to present the drug
discovery process as a continuum -- an essentially linear process
that begins with genes, and moves through proteins of therapeutic
interest that are encoded by the genes, to small molecules (potential
drugs) that are designed to modulate the function of the target
proteins. At the genetic end, the problem most suited to computing
(and particularly, supercomputing) is hunting for sequence similarities
between known genes and the entire genome database. The vast
amount of data from sequencing the human genome and those of
pathogens means that this is an enormous computational task.
A recent example of the types of discoveries that can be made
from such data mining is the identification of the similarity
between smallpox viral genes and some of the genes in the human
immunodefense system. It is clear at this point that the rapidly
increasing amount of genetic data that are becoming available,
coupled with the increasing reliance of pharmaceutical companies
on the selection of drug targets based on information contained
in these databases, will translate to substantial opportunities
for improvements in bioinformatics algorithms.
Moving along the continuum, the greatest scientific challenge
remains the `protein folding problem' -- going from gene sequence
(and therefore protein sequence) to protein structure. Sequence
identification far outpaces experimental structure solution,
so there is a need to predict structure from sequence. Folding
must depend on sequence and physics, but new insights and methods
are needed. This remains the "Nobel Prize" problem.
Moving from protein targets to the small molecules that are
being designed to bind to them, it is noted that such molecules
are increasingly being synthesized by combinatorial or highly
parallel synthesis techniques. While such methods are able to
generate molecules on a scale of tens to hundreds of thousands,
there is a need (and a recent trend) to reduce the structure
space somewhat by clever application of computational methods
to achieve greater focus and to improve the odds of identifying
active compounds. This also carries over to the need for more
efficient methods for comparing and selecting molecules (with
specified properties) from databases containing hundreds of
thousands of "real" compounds, to billions of "virtual" compounds
(currently existing databases), each of which can have many
conformationally-accessible structures. It was noted in the
workshop that organic structure-space, of molecular weight less
than 500, has been estimated variously as from 1060
to 10400 unique compounds.
Doug Rohrer's focus was in the "small molecule" region of the
continuum. He noted that many of the current challenges in making
sense of structure-activity relation (SAR) data relate to choices,
and that a large number of choices are generally required. To
name a few, these choices range from selection of compounds,
generating 3D structures for each compound (the conformational
flexibility problem), determining the most appropriate overlay
of the compounds (alignment rules), defining a consensus multi-molecule
binding model, and determining how the consensus features of
the model can best be used in drug discovery and optimization
(that is, now that we have a model, what do we do with it?).
The initial choice of compounds used to develop an SAR model
typically encompasses a small number of highest-affinity compounds.
However, as the project matures, the selection of additional
compounds must include as much diversity as possible, in both
the 2D (connectivity) and 3D (spatial) sense. The challenge
is to evaluate this diversity quickly. It is important, as was
mentioned numerous times during the workshop, to maintain a
fast turn-around time on such studies in order to remain in
the decision and design loops. Otherwise the chemistry will
move ahead without it. Doug suggested that perhaps improved
graph theoretic approaches could be applied at this stage.
Usually the compounds of interest can have numerous low energy
conformations. The challenges here involve methods for exploring
conformational space, followed by analysis to select a representative
subset of diverse conformations. Several novel methods were
presented at the workshop which may address this challenge.
One involved reducing the 3D structures to a 2D format that
retains more information than does a simple projection technique.
Modifications of alphanumeric character recognition algorithms
were then used to identify similar shapes. Another technique
that was presented involved mapping the structures into pre-defined
arrangements of spheres to classify the shape of the molecules.
Such classification of the molecular shape could provide a starting
point for the production of multiple molecule overlays to generate
the SAR model.
Field-based similarity matching provides an excellent means
of optimizing structural overlays. However, the speed of this
process needs to be improved in order to be useful with larger
numbers of molecules (greater than ten). In addition, information
about the relative biological potencies somehow needs to be
factored into this process, so that the good, the bad, and the
ugly features of the overlay model can be identified.
Finally, methods to use the overlay features of the SAR model
to derive new molecules algorithmically, to test hand-generated
molecules against the model, or to optimize existing leads via
suggestions from the model, would be the ultimate goals. Automated
de novo design programs like GROWMOL might be a start,
but the solution is still elusive.
Bill Dunn continued the discussion of challenges related to
small-molecule design, and again, for the common situation where
the 3D structure of the target (protein) is not known, leading
to the application of indirect methods in the delineation of
3D quantitative structure-activity relations (QSAR). One difficulty
with these methodologies (e.g. comparative molecular field analysis,
molecular shape analysis, etc.) is the assignment of a receptor-bound
conformation (conformational flexibility again) and an alignment
for the ligands (overlay problem). This is generally done by
trial and error, with some guidance provided by ligands with
restricted degrees of conformational freedom. This is an extremely
costly exercise that limits the utility of 3D-QSAR.
A general solution to this problem may be found by relaxing
the conformation and alignment constraints of existing approaches,
and by describing the active ligands with features that vary
with conformation and alignment. The resulting arrays are third-order
tensors that can be decomposed to yield the descriptor vector(s)
most highly correlated with biological activity.
Dunn's group is exploring a general formalism for 3D-QSAR that
includes various methods useful for the decomposition of 3-way
arrays of conformation- and alignment-dependent feature data.
They are also exploring novel methods of aligning sets of bioactive
compounds, in such a way that leads to an unconstrained 3D-QSAR
Dave Doherty focused on problems in biological chemistry that
are characterized by structural transitions that involve large-scale
motions of portions of the structure. One obvious example of
this is the folding of proteins. But there are other, less global,
changes that also occur via large scale motions, and Doherty's
statement of the problem of identifying these transitions was
aimed at discovering cooperative or nonlinear effects that cause
such large scale motions. Definitive answers to these questions
would contribute greatly to our understanding of protein structure,
and particularly to our ability to predict tertiary structure
and its longer time-scale behavior.
The issues that he raised were intended to provoke thought among
the mathematicians and drug designers about how further improvements
in solutions to nonlinear mathematical systems might shed some
light on current problems in drug design. To motivate such thought,
an example was given of some of his studies that used direct
molecular dynamics simulation to search for nonlinear motions
that have long been postulated to be characteristic of the so-called
"rotator" pre-melting phases in n-paraffin crystals
(Doherty, D. C., Hopfinger, A. J., Phys. Rev. Lett.
(1994) 72 (5), 661). These "sine-Gordon" soliton waves
arise from the solutions to a set of nonlinear differential
equations. The fact that these equations have an analytical
solution (a traveling arctangent waveform) provides a unique
opportunity to search for these cooperative motions using direct
simulation. This work appears to have definitively identified
these high amplitude, localized waves in the molecular dynamics
simulations, even though there is no explicit term in the molecular
mechanics force field that specifically gives rise to them --
which is indicative of the cooperative effects of a collection
of multiple chains.
This is an exciting development in our understanding of cooperative
effects in molecular phase transitions. So, to the attending
mathematicians one might ask, "What are the current developments
in solutions (analytical or simulated) to molecular dynamics
equations for complex systems that may be of some use in our
understanding of cooperative processes in biochemical systems?"
And one might ask the computational chemists, "What are the
important questions that might move us along to a better understanding
of cooperative effects, through some combination of mathematics
and direct simulation?"
After the panelists' presentations and the ensuing discussions,
additional challenges were put forth by other workshop participants.
It was noted that few of the issues discussed to that point
related to what has become known as `direct methods' -- techniques
such as docking, de novo design, ligand-binding scoring,
and so on, that can be applied when the target protein is known
in structural detail. Such detailed knowledge is becoming much
more common, in part because of the rapid emergence of genomics-based
targets. In many pharmaceutical companies, all new discovery
programs are molecularly-based, and they follow the continuum
outlined by Graham Richards. Genomics is used to select the
target, which is then further developed through cloning, expression,
folding, and purification of the relevant protein(s) to produce
molecular (and generally, high throughput) assays of small-molecule
activity. With protein on hand, structural biology (X-ray crystallography,
NMR structure determination, antibody epitope mapping, and so
on) can provide the structural detail needed for application
of direct methods to the task of lead discovery, or at least
to lead optimization. (An "epitope" is the surface region of
another molecule that is recognized and bound by an antibody.
A "lead" is a compound with the sought for bioactivity, but
which requires further optimization, for example to improve
its bioavailability or eliminate certain side reactions, in
order to become a useful drug.)
A number of the important issues in this area were discussed
in the main workshop presentations during the week. One of the
most pressing issues was improved methods for dealing with the
physics and physical chemistry of water, sometimes through explicit
consideration of solvation effects during simulations or binding
energy calculations, but more typically through continuum solvation
models. It was stated by one of the participants that we can
generally do quite well now in predicting geometries of potential
drug molecules at a binding site, but not so well in accounting
for their solvation effects on the binding energy or even for
the intrinsic components of the binding energy. Accurate calculation
of ligand/protein binding energies (including entropic considerations)
was generally viewed as one of the most important current needs,
as it pervades all of the direct-methods techniques for studying
and predicting the activity of small-molecule analogs. It was
also noted that, in order to remain within the design cycle,
molecular modelers must choose their methods, in part, on the
basis of speed, to provide quick turn-around of results. This
places a greater burden on finding energy-based methods or scoring
functions that are accurate and fast. The need for
speed is most evident in the effective application of automated
de novo design methods, where tens to hundreds of thousands
of candidate structures must be generated, evaluated (by some
form of scoring function which assesses goodness of fit to the
target), and assigned a priority ranking. Of course, when opting
for methods that are fast, one must always question whether
the reliability of the results warrants the use of the faster
Another participant went further and pointed out that many of
the currently available methods typically produce huge lists
of seemingly reasonable molecules. However, only a few can be
chosen for synthesis. Ideally a free energy scoring function
would provide a basis for ranking and selecting the structures.
Despite much progress, this remains an unsolved problem. Although
the list can be reduced, one cannot with confidence pick only
the top ten or so compounds for further study. Until the perfect
scoring function is developed one must sample the reduced list
in some rational manner. Experimental design methods are needed
to address this. This is an opportunity for closer collaboration
between the computational chemistry community and the statistical
and applied mathematics community.
the University of Minnesota (Chemistry and Supercomputer Institute)
was one of the organizers for the workshops on "Evolutionary
Algorithms" and "Mathematical and Computational Issues in Drug
Design." He together with W. Jeffrey Howe, Anthony J. Hopfinger,
Jeff Blaney, and Richard A. Dammkoehler write the following
foreword for the IMA Volume on "Rational Drug Design."
Drug research and discovery are of critical importance in human
health care and are becoming increasingly expensive, while the
need for new drugs is also increasing. Computational approaches
for discovery and optimization of drug leads have proven successful
in many recent research programs. (A "lead" compound is one
with sought for bioactivity but which requires further optimization,
for example to improve its bioavailability or reduce certain
side reactions, in order to become a useful drug.) Methods for
drug lead discovery and optimization have grown in their effectiveness
not only because of improved understanding of the basic science
-- the biological events and molecular interactions that define
a target for therapeutic intervention -- but also because of
advances in algorithms, representations, and mathematical procedures
for studying drug processes. In order to promote the interaction
of mathematicians, computer scientists, and chemists to further
the progress in the field and alert researchers to the opportunities
for interdisciplinary research, the University of Minnesota's
Institute for Mathematics and Its Applications and the University
of Minnesota Supercomputer Institute sponsored a Workshop on
Rational Drug Design on the Minneapolis campus, April 7-11,
1997. The workshop was devoted primarily to mathematical and
computational issues in drug design. This volume contains the
proceedings of that Workshop.
The workshop brought together top researchers in computer-aided
drug discovery, computational chemistry, mathematics, and computer
science to present state-of-the-art research in both the science
and the underlying mathematics and to identify new problems
for possible collaborations. General subject areas of the workshop
included receptor-based applications such as binding energy
approximations, molecular docking, and de novo design; non-receptor-based
applications such as molecular similarity, conformational analysis,
and structural diversity; molecular dynamics simulations; and
solvation issues related to partitioning of a solute between
aqueous and nonpolar media. The workshop focused on the mathematical
procedures and algorithms upon which the scientific applications
are based. These include graph theory and topology, non-linear
multidimensional optimization, the processing and representation
of information obtained from simulation studies, global optimization
and search strategies, plus performance enhancement through
parallel computing architectures. In addition to the oral presentations,
the workshop included two panel discussions, one examining the
most important current problems in drug design that may be computationally
tractable, and the second focusing on emerging areas of study
in which improvements in scientific knowledge over the next
few years may enable the fruitful application of computational
methods. The overall goal of this workshop was to bring together
scientists and mathematicians to examine the current state of
this very broad and interdisciplinary field of research, and
to identify the areas where cross-fertilization of ideas and
collaborative research might most effectively advance the field.
A broad landscape of high-profile topics in computer-assisted
molecular design (CAMD) directed to drug design were covered
over the course of the Workshop. Several of these topics involve
finding working solutions to problems where mathematicians and
mathematically oriented physical scientists might provide new
direction and insight. Among the problems presented were two
which permeate many fields of research today. One of these two
problems is sampling high-dimensional spaces. In CAMD applications,
sampling problems arise in performing conformational analysis,
searching for molecular alignments, and carrying out molecular
simulations. The other of these two problems is determining
all extrema of a high-dimension functional interrelationship.
Identification of stable states (conformations, crystal structures,
and ligand-receptor binding modes) corresponds to finding minima
in potential energy functions; barriers to reaction, conformational
interconversion, and melt transitions correspond to saddle points.
Optimum structure-activity relations correspond to extrema of
penalty functions or of average deviations of prediction from
experiment in correlation models.
The construction of correlation models actually presents a whole
family of mathematical problems identified at the Workshop.
The most direct CAMD application area in correlation model construction
is quantitative structure-activity relationship (QSAR) analysis.
Central to the construction of QSARs is the maximum extraction
of information from data sets which are highly oversubscribed,
that is, for which the number of independent variables is much
greater than the number of dependent variables, as is the case
for applications of comparative molecular field analysis (CoMFA).
The opposite case, the number of independent variables being
much less than the number of dependent variables, an undersubscribed
problem, is also of concern. Here the issue is to get the most
representative, robust, and reliable model from the data set.
The multiple extrema problem also arises in constructing statistical
models. Data sets can contain multiple stable correlation models.
There is a need to know how many distinct models are inherent
to the data set and to be able to rank those models with respect
to measures of significance, reliability, and robustness.
Theory can also contribute to expanding the data set by producing
theoretical data to characterize potential drug molecules that
have never been made. Use of force fields to determine the likely
steric and electrostatic fit of a proposed molecule to a binding
site is the most prominent example. An example of a frontier
in this area was a paper on the use of quantum mechanical modeling
to calculate charge distributions, solvation energies, and partition
coefficients for small molecules.
Many of the opportunities for new mathematical contributions
to this field are occasioned by the recent prominence of combinatorial
libraries. Such libraries can be synthesized and assayed by
robots, but mathematical modeling can play a very important
role in prioritizing the targets to be made and making sense
of the results. Because very large numbers of molecules can
be involved, there is a new emphasis on rapidity and efficiency
of the computational tools.
In a stimulating after-dinner speech at the Workshop banquet,
Dr. Ralph Hirschmann of the University of Pennsylvania drew
on his long industrial experience to present another perspective
on drug design, focusing on many non-computational issues. For
example, he discussed a 1997 paper in the Journal of the
American Chemical Society where researchers found that
the shape of a base inserted in DNA, rather than its hydrogen-bonding
ability, may be the key to the polymerase recognition process
that leads to faithful copying of DNA. Although this is an experimental
result, by underscoring the role of 3-D shape it further dramatizes
the role that computation can play in designing biotechnological
molecules that mimic one or another capability of natural biological
molecules. Dr. Hirschmann, however, took exception to the use
of "rational drug design" and "computer-aided drug design" as
near synonyms; he claims that pharmaceutical researchers were
not totally irrational before they had computers! While this
may be true, we hope that the Workshop and these proceedings
will continue the trend of more and more productive uses of
mathematical and computational techniques for the eminently
humanistic goal of the design of new and better drug molecules.
of the University of Minnesota, School of Mathematics and Minnesota
Center for Industrial Mathematics writes:
The IMA held a Special Workshop called "Template-Driven Automatic
Differentiation for Large-Scale Scientific and Engineering Applications"
from June 29 to July 3, 1997. The workshop was organized by
Tom Coleman (Cornell), Bill Symes (Rice) and Fadil Santosa (Minnesota),
and was partially supported by the Cornell Theory Center and
the Center for Research on Parallel Computation at Rice University.
The goal of the workshop is to bring together developers of
a number of widely available Automatic Differentiation (AD)
programs with scientists who would like to use AD in their work.
The application areas include control problems, inverse problems
and parameter estimation. The AD packages discussed (and used)
in the workshop include ADI-C, ADIFOR, Odyssee, TAMC, PADRE2,
What is novel about this workshop is that the organizers posed
4 typical problems that call for AD, and work together with
the participants to produce "boiler plate" codes that uses AD
in their solution. The workshop was successful in that it informed
the AD developers the needs from the application side. Moreover,
we have created a resource for others who want to use AD by
providing them, through the web, carefully documented information
about how to use the AD tools. It is hoped that the workshop
has succeeded in lowering the potential barrier to using AD
in important scientific applications.
3. SOFTWARE DEVELOPERS
the April 21-15 IMA Tutorial on PDE SOFTWARE, eight software
packages were presented by the developers or co-developers of
Stefan Turek of the University of Heidelberg presented FEAT;
Hans Petter Langtangen of the University of Oslo presented DIFFPACK;
Olivier Pironneau of the Université Pierre et Marie Curie,
Paris presented FreeFEM;
Lars Langemyr of COMSOL, Sweden presented the MATLAB PDE software;
Hidehiro Fujio of Nippon Electric Corporation presented FEEL;
Barry Smith of Argonne National Laboratory presented PETSc;
Randy Bank of the University of California at San Diego presented
Henrik Rentz-Reichert of the University of Stuttgart presented
After the tutorial, the developers were asked to respond to
the following questions:
Which software package did you present?
Did you try any software packages on the benchmark fluid problem
that Rannacher proposed [Navier-Stokes flow through a square
channel past a slightly off-center transverse cylinder]? Please
assess the software packages you tried (please mention, for
example, whether your comments refer to ease of use or to
Did you try other software packages on other problems? Please
describe the problems and your assessment of the software.
Please make any other comments on your software and on the
other software packages.
Please make any comments about the organization of the workshop.
The developers were told that "We will not use your name in
any report, so you may feel free to comment honestly. Of course,
we assume you will report differently regarding the software
you or your group presented."
Their comments are below, without attribution, arranged in random
order by general topic. Comments on a developer's own software
have not been included here.
COMMENTS ON THE DIVERSITY OF SOFTWARE PACKAGES:
is a modest package compared to most of the others. As a research
code, its strongest point is that it employs at least a few
"cutting edge" algorithms at any given time, and is continuously
being revised and updated.
software packages are designed for:
and have to be realized with completely different emphasis.
Software designed for the third case, Industrial application,
mainly stresses the efficiency of the software and the algorithms
behind the software.
I tried FEEL, UG and Matlab. as a software developer I do
not like to assess software based on an hour of experimentation.
some of the packages(like Matlab) are designed to be useable
within some hours, others(like UG) are designed to be a good
and efficient scientific tool after a period of training that
may last for months. for researchers the latter type of tools
are often more valuable in the long run because the limitations
are usually much smaller.
are so many kinds of PDE software, because their purpose and
the levels are different, like MATLAB (see PDE solution) -
freeFEM(numerical analysis)-UG(practical-usage) -PETSc(parallel
computation tools). So, it may be quite convenient for the
user, if each system has entry or output interface to another
COMMENTS ON OTHER DEVELOPERS' SOFTWARE:
one asks for my very personal opinion about the software that
was presented at the IMA workshop, I think UG and PETSc were
the most impressive packages. Both of them might get bad rating
from those who tried them at the IMA for an hour or two, but
I know that these packages are fantastic tools in the hands
of professional programmers that solve complicated and non-standard
PDE problems. These packages also contain novel design principles
and have a clear vision for what scientific computing software
should be. The "optimal PDE software" should use packages
like these as the computational engine, combined with further
developments of the nice easy-to-use GUIs and problem specification
languages that we find in, e.g., the Matlab PDE toolbox, FEEL,
tried freeFEM for Stokes' problem, structural analysis and
convection- diffusion problem. The input format of freeFEM
made it quite easy to try freeFEM for various problems. I
also tried Diffpack, and MATLAB, with their pre-defined sample
It is quite easy to use MATLAB type softwares, because we
have only to specify coefficients of 2nd order problems,
so they are very good for just looking the solution of PDEs
for educational purposes. But, for further users those who
want to study numerical analysis, I think the interfaces
of freeFEM or FEEL are suitable. Though these interface
require the knowledge of numerical analysis, with these
systems, the user can learn and try the numerical solution
of PDE without pain, like debugging, prepare data files,
make interface to graphical outputs, etc. Because numerical
analysis is not only a mathematical theory but a practical
technique of computation, the knowledge of disretization
and computation should be required to the users. And for
practical usage, I think the interface of UG is quite attractive.
Once the problem is fixed, batch language with data control
may be efficient.
NEC example (stabilizing a convection-diffusion equation stable
by means of streamline diffusion) was very nice to run. I
also liked the idea (in FEEL) of generating FEM-code from
a meta-language driven code-generator very much. If this language
is open and extendable (using a parser generator like lex
& yacc) and combining it with efficient and solvers that are
also open and extendable this could be a powerful tool for
the numerics of PDE.
FEATFLOW is a very efficient flow solver but lacks of adaptivity
and parallelism. Probably it is also hard to study other PDE-systems
since the FORTRAN-code is very old fashioned. the same comment
applies to PLTMG (except that it handles a scalar equation
rather than systems of PDE) PETSci is only a parallel solver
toolbox. I think it is pretty hard to make good use of it.
combines Multigrid, adaptivity and parallelity in a modular
and easily extendable system in a way that allows to study
all kinds of PDE with FEM/FVM discretizations. It offers a
large set of standard solvers and allows an easy transition
to parallel architectures. On the other hand it is most likely
that a user will have to write new code for its application
and it probably will take him several months to get into it.
ON IMA WORKSHOP:
my limited time at the workshop, it seemed to be well organized.
I appreciated the idea that the codes chosen for workshop
represented a very broad spectrum of philosophies. The relaxed
atmosphere and open discussion was also a very nice aspect
of the workshop.
organized. It was an opportunity to see what others are doing
and this is not so easy because stuff is usually not published
but posted only on the web (and I am not a web surfer, time
workshop was excellent (!!!), but I think the aim that everybody
works during the breaks with the proposed packages is an illusion.
I hope, such a meeting is repeated very soon!!!!
workshop was very well organized. In my opinion (and many
others that I talked to), all the presentations were of unusually
high quality. The mix of overheads and live computer presentations
was new to the speakers and the audience and turned out to
be very effective. Together with the prescribed composition
of the talks, the breaks dedicated to exercises, and the summary
("lessons learned") at the end, this workshop contained some
truly novel features that I hope we will see more of in the
future. Petter Bjørstad did a great job in coming up
with this original concept for a workshop on software and
for organizing the meeting.
Almost all the packages were developed at universities.
Software development gives, unfortunately, very little credit
for anyone working or studying at a university. The possibility
of giving talks at workshops/conferences and writing papers
about the software development is therefore important if
we want the universities to play a fundamental role in future
software development. This workshop contributed nicely in
this direction. Fortunately, the interest in software development
techniques has increased dramatically during the last years,
and many of the international conferences on PDE related
material have minisymposia dedicated to software issues.
This is also an indication that it was appropriate for the
IMA to organize a workshop on PDE software.
talks would appeal to a large group of researchers in applied
math, numerical analysis, physics, astrophysics, geophysics,
mechanics, various branches in engineering etc. It is therefore
a pity that the audience was quite small. This was indeed
a workshop that could attract interest far beyond IMA visitors
and the applied math community. My suggestion is to repeat
this PDE-SW workshop every two year, for example, increase
the number of speakers, move hands-on experimentation to an
evening session where the speakers are available for assistance,
allow for commercial software as well, require all presentations
to available on the web, and put much effort into advertising
the workshop and attracting people from a large number of
fields. With the web, the workshop will in fact be "available"
to the whole PDE community. In this way, the IMA could be
a center for math software and thereby increase the general
interest in the institute and hopefully also the financial
enjoyed the workshop very much and learned a lot about other,
comparable packages. My suggestions for future workshops of
this kind is to do the examples in a computer pool where the
tutor can answer questions where they arise. This will also
yield an atmosphere of general discussion amongst the participants
that is not possible when people sit insulated in their offices.
of IDA/Center for Computing Sciences was a speaker at the November
11-15, 1996 workshop on "The Mathematics of Informational Coding,
Extraction and Distribution." His comments on "Massive Data
I will address some of these issues I see, but not with all
the formal structured presentation of a finished report. (That
is, I reserve the right to ramble a bit.)
This is less important than some of what follows, but is worth
saying. Much of this work will be "mathematical" but will
not be "mathematics" as the term is currently understood.
In that sense, it is not what postgraduate research mathematicians
would have expected to do. On the other hand, it is
exactly the sort of work that one would expect bachelor's
and master's level mathematicians to do. This should be viewed
as an opportunity for research mathematicians, not a hindrance.
If mathematics involves studying the abstract structure and
logical interrelationships of things, surely it is good for
mathematicians to be involved in work that is mathematical
and exposes them to entirely new universes of "things" that
must have structure? There may be a delay before it becomes
possible to raise the level of abstraction to the point that
a "mathematics" of these structures is synthesized from experiential
information, but there isn't really anything fundamentally
wrong with applying familiar logical processes and skills
in trying to understand the complexities of new things.
There are some things that are different from normal academic
mathematics. Not better, or worse, but just different in ways
that should be kept in mind.
These are large scale projects.
These are real projects, i.e., there are people who care not
about studying the problem, or proving theorems about the
problem, or studying the abstract versions of the problem,
but about the actual outcome of computations in this particular
The details involved in the specific projects are vitally
important and one cannot (at least not at present) abstract
away the details without becoming vacuous. For example, we
saw on Wednesday two examples of what resembles a transitive
one is constructing or using a thesaurus. In one sense,
this consists of a graph with a node for each term and (directed?)
arcs with weights (normalized from 0 to 1?) representing
the extent to which one word is "connected" to another.
One way of looking at a thesaurus is as the transitive closure
(with some sort of thresholding and/or attenuation functions
based on distance?) under "connectedness."
Suppose one is trying to determine which phone numbers have
fax machines connected. The same approach as above is basically
what could be done.
But I maintain that beyond the brief and almost-too-obvious
description above, there probably isn't much real commonality
between what gets computed to solve the two different problems.
The details don't just matter, they matter almost more than
anything else. The connectedness functions will differ, being
based on the nature of language, the statistics of the 130,000
words in common English usage, the statistics of telephone
calling patterns, etc. The attenuation functions will matter.
The size of the data bases will matter-things one might get
away with in processing 130,000 English words might be infeasible
in dealing with (how many millions a day was it?) phone calls.
As Grossman more or less said but didn't quite say this way,
if you don't know how to measure the scale of these projects
based on the number of seconds in a year, you probably aren't
thinking about them in the right way. Similarly, to follow
up on what Wegman implied but didn't say outright, it is important
to measure the cost of these computations in appropriate units.
These units are wall clock times-seconds for an interactive
response, CPU hours/days/weeks/months for a massive preprocessing
step, etc. The units are NOT O(n1.5) steps
in an algorithm. Although an O(n1.5) algorithm
might be considered "quite nice" by the J. Random Scientist
who is really interested in getting the problem solved, what
would really stimulate J. Random's endorphins is
an O(n1.5) algorithm that when implemented
dropped the execution time on a 108 size data set
from the 107 seconds (4 months) on a 1 gigaops
machine with an O(n2) algorithm down to
1000 seconds (17 minutes) on the implemented O(n1.5)
is also very important to remember that the details of each
application are probably vital to the eventual successful
solutions. One of the hardest things for me to understand
when, after having been trained as a pure mathematician, I
suddenly became in 1977 a computer science professor, is that
there didn't seem to be any theorems anymore, only examples.
The "theorems" or general truths about how to compute things
were vague or contradictory, and in spite of this vagueness
there were good things being done based on the phenomenology
of each specific problem.
One can easily produce all the reasons why virtual memory
should and shouldn't work (a) If a page in memory has not
been used recently, it is from a previous part of the program
and won't be executed again and can be swapped out...or else
(b) the page not recently referenced is from the top of a
loop whose bottom part is just finishing up being executed
so the page in question is just about to referenced again
and better not be swapped out.) But virtual memory does
work, because the operating system as written is tailored
to the specifics of the computer architecture as designed
and because, in spite of the fact that it is easy to write
an individual program that will cause any given machine to
thrash, the phenomenology of the execution characteristics
of "most" real programs is such that virtual memory, with
some caveats, does in fact work.
line from the above:
I believe this whole area should be approached from the bottom
up and not from the top down. That is to say, DMS should attempt
to clone successful massive data set activities with mathematicians
as important members of the research teams rather than trying
to create, ab initio, a massive data sets initiative in the
mathematics community. Over time no doubt the math community
would learn inductively from its experience, and some more
traditional mathematics might follow, but this work is problem
driven, and mathematics per se simply doesn't have the problems.
The purpose of the MACHO experiment was not to collect and
analyze lots of data. The purpose was to do astronomy. The
only reason we heard about the problem is that the computational
problem on the data has become the bottleneck preventing further
work in astronomy. Similarly, the growing problem on the net
is making some sense out of all ~the "stuff" that's out there.
The stuff that people want to get to is out there, but not
being able to compute a semantic organization to all that
stuff is getting in people's way.
So I think the effort has to be problem driven, and probably
therefore has to be done in collaboration with the other areas
that "own" the problems.
from Rensselaer Polytechnic Institute (Mathematical Sciences)
was a visitor from January 1 - June 30, 1997. Her report follows:
I certainly had a wonderful visit there at the IMA. I hope
you're doing well!
My first order of business was to finish revisions to a paper
 I had begun during my previous IMA visit. This paper is
joint work with Paul Bigeleisen, an anesthesiologist who at
the time was working at St. Paul - Ramsey Medical Center in
St. Paul. This paper develops a mathematical model of the
breathing circuit used to administer anesthetic gases to patients.
We then used the model to answer some open questions about
the best way to replace lung nitrogen by oxygen before surgery.
I spent quite a bit of time working on the problem of proving
that measurements on a plane uniquely determine the medium
parameters of an inhomogeneous half-space. This work is joint
work with Matti Lassas, whom I had met at the IMA during my
1994-1995 visit. We finished the proof  when we were together
at a conference in July 1997. I wrote a book review for Inverse
Problems on Andreas Kirsch's new book. I spent a good part
of June writing a paper on inverse boundary value problems
for American Scientist magazine .
I especially enjoyed the opportunity to get to know Petter
Petter Bjørstad, Ralph Kleinman, and Frank Natterer.
Although I haven't actually initiated any specific joint projects
with Natterer, I'm particularly interested in the work that
he is doing. As a result, I visited him and his group in Muenster
in March. One of the students I met there, Oliver Dorn, has
been working on inverse transport problems, and is now at
Stanford. I recently suggested Dorn's name to a Duke electrical
engineer (Larry Carin) who is thinking about millimeter-wave
penetration of foliage and wants to use a transport equation
model. It's hard to point to specific results of these personal
relationships, but they certainly contribute to the health
of the scientific enterprise. I also enjoyed getting to know
Sheri Moskow. Maybe at some point I'll be able help her career
I audited two classes in the Minnesota Electrical Engineering
department, namely "Microwave Circuits and Devices" and "Antenna
Theory and Design." This is part of my continuing campaign
to learn more about radar and the associated inverse problems.
I learned about beam-forming techniques in acoustics. This
is a key part of the side-scan sonar technology. I read Yu
Chen's recent preprints on his stable algorithms for solving
multidimensional inverse problems. I studied Frank Natterer's
algorithms, and induced him to try his method on Yu Chen's
examples. I understand that this led Natterer to some improvements
of his algorithm. At Ralph Kleinman's and my urging, Frank
also tried his method on some problems with caustics, with
 P. Bigeleisen and M. Cheney, "Models for an anesthesia
breathing circuit," IMA preprint 1476.  M. Lassas and M.
Cheney, "Uniqueness for a wave propagation inverse problem
in a half space," in preparation.  M. Cheney, "Inverse
boundary value problems," American Scientist, 85 (September-October
from University of Utah, Medical Imaging Research Lab, Department
of Radiology was a long-term participant. He was also a speaker
during the March 17-21, 1997 workshop on "Computational Radiology
and Imaging: Therapy and Diagnostics." He writes:
I wanted to drop a quick note of thanks for the hospitality
I have enjoyed here at the IMA for the month of March. I was
very pleased to get the invitation (as you see, I took advantage
of the maximum stay!) and I had a very productive time, collaborating
with colleagues and pursuing interesting research projects
I have long put off.
The facilities here are excellent. The office space (I don't
have a window in my university office), the computer systems
with full Internet access, the coffee room, all really don't
leave any excuse. You HAVE to be productive in this environment!
I am very impressed by the courteous and professional attitude
of all the staff. I interacted at least once with each of
the groups: office, accounting, computer systems, and TeX
experts, and they were all very helpful, especially the office
I will probably be taking further advantage of your staff
when I try to TeX (IMA-style) my report for the proceedings.
from the University of Minnesota (School of Mathematics) reports:
During year 1996-1997, the IMA activities focused on the topic
`Mathematics in High Performance Computing.' The reduced teaching
load I was awarded by the School of Mathematics allowed me
to strongly interact with several visitors. In particular,
I had the opportunity to strongly interact with J. Flaherty,
Pierre A. Gremaud, Mirko Rokyta, Chi-Wang Shu, and Endre Suli:
(1) With J. Flaherty, we started a project centered around
the first mathematically sound adaptive methods for nonlinear
(2) With Pierre A. Gremaud, we were able to finish a paper
devoted to a priori error estimates for nonlinear conservation
(3) With Mirko Rokita and Endre Suli, we started a very promising
project whose aim is to devise error estimates for convection-dominated
problems in bounded domains.
(4) With Chi-Wang Shu, we finished two papers. One concerning
a computationally intense study of discontinuous Galerkin
methods for nonlinear hyperbolic systems, a project we started
five years ago; and the other, concerning the devising of
discontinuous Galerkin methods for convection-dominated flows.
This second paper is the first in a series in which we will
study these methods for convection-diffusion flows.
(5) With Chi-Wang Shu and Endre Suli, we started a long-term
project devoted to the study of new a priori and a
posteriori error estimates for finite element methods
for hyperbolic systems. This project strongly links the research
groups at Providence (Shu), Oxford (Suli) and Minnesota.
As you can see, my participation in the IMA activities was
greatly enhanced by the reduced teaching load I received from
the School of Mathematics.
of Universite Joseph Fourier (d'Informatique) was a visitor
from March 1-29, 1997. He participated in the workshop " Computational
Radiology and Imaging: Therapy and Diagnostics." His report
I was very happy to have the opportunity to work with David
Walnut on sampling problems and to have very nice discussions
with T.E. Quinto on the rotational invariant generalized Radon
transform ant its application in astronomy and Rolf Clack
on 3D tomography. I had also some time to start to write my
habilitation thesis, and it was very good to be far from France
for such activity. The IMA is really a wonderful place to
do research with very nice people. I really enjoyed to spend
more time with them than just the few days of a congress.
Once again, thank you very much for the invitation. It was
In tomography a function is reconstructed from its projection.
It is mainly a medical imaging techniques and a non destructive
control industrial method. Because of the star rotation tomography
is also encountered in astronomy. Sampling conditions of the
measure are in practice necessary. In tomography, the essential
support of the Fourier transform of the Radon transform (in
2D) and the X-ray transform (in 3D) have particular geometries
that can be used in order to produce regular efficient sampling
schemes generated by a non singular matrix W satisfying the non overlapping Shannon
conditions. In 2D the interlaced scheme has been proposed
by Cormack, Rattey et Lindgreen, Natterer (in particular for
fan-beam geometries), in 3D we have proposed in  the sampling
condition of the X-ray transform
in the unit circle and ,
more precisely of
This is the geometry of nuclear imaging when the gamma-camera
turns around the patient with a parallel collimation. A. Faridani
and D. Walnut have proposed new sampling theorems for non
regular schemes, that yields new sampling schemes useful for
Our recent work thus concerns 3D . During our stay in IMA
we could prepare with Rolf Clack the post-doc project in Salt
Lake city of a very good french student, Catherine Mennessier,
on reconstruction from incomplete projections. Its PhD in
astronomy has allowed to establish the link between Doppler
imaging and the rotational invariant generalized Radon transform.
I had a very helpful discussion with E.T. Quinto at IMA: its
invertibility proof can be partly adapted to Doppler imaging.
When the rotational invariant weigh function is polynomial
(with low degree) the interlaced sampling is shown to be efficient.
This can be applied in certain geometries of Doppler imaging.
I could also work with David Walnut on multidimensional sampling
on unions of lattices, which could have very nice practical
applications in tomography.
L. Desbat. Efficient sampling on coarse grids in tomography.
Inverse problems, 9:251-269, 1993.
L. Desbat. 3D efficient parallel sampling perturbation in
tomography. In International Meeting on Fully 3D Image
Reconstruction in Radiology and Nuclear Medicine, 1997.accepted.
L. Desbat. Echantillonnage parallhle efficace en tomographie
3D. C.R. Acad. Sci. Paris, Séerie I, t. 324,
pages 1193-1199, 1997.
L. Desbat and C. Mennessier. Efficient sampling in Doppler
imaging. Proceedings of SampTA, 1997. accepted.
of the University of California (Pharmaceutical Chemistry)
gave a presentation at the workshop on "Mathematical and Computational
Issues in Drug Design held on April 7-11 1997. Below is report
on his successful collaboration with other mathematicians
and computer scientists.
About 2 years ago, I have a talk at an IMA on Protein Folding.
Two computer scientists from the University of Minnesota were
in the audience - Professor Ben Rosen and his former student
Andy Phillips, now Associate Professor at the Naval Academy.
They were working on a global optimization method they felt
might help us with protein folding. We stated a collaboration.
About 3 papers have resulted from this collaboration so far
and we are now beginning to prepare a grant proposal. It's
an Assistant Professor at Mathematics Department of the University
of Tennessee at Knoxville writes:
From April 1 to June 30, 1997 I was a resident of the IMA
for participating 1996-97 IMA program: Mathematics in High-Performance
Computing. This was my fisrt visit of the IMA. To summarize
my three month experience at the IMA using one word, I would
like to say "wonderful." Indeed, the three months I spent
at the IMA was the most memorable and the most productive
period of time for me in my five year academic career. I enjoyed
very much the IMA's unique environment, conferences, workshops,
short courses, seminars, and especially, meeting and communicating
with other IMA visitors.
My research areas are computational and applied mathematics
with applications in fluid and solid mechanics and geosciences.
Mathematically, most problems I am interested in are described
by a set of linear or nonlinear partial differential equations,
hence, the core of my research involves analytical analysis
of solutions of the differential systems and developing efficient
(sequential and/or parallel) numerical methods to compute
the solutions on high-preference computers, which is the theme
of the IMA program in Spring of 1997.
While I was at the IMA, I had been worked on two research
projects. The first project is to finish a ongoing project
on computing wave propagation in unbounded domain using artificial
boundary condition approach. In this approach the unbounded
domain is truncated into computationally feasible finite domain,
so finding the right boundary conditions on the artificial
boundary is the key step of the method. The work I did at
the IMA is to test numerically a class of artificial boundary
conditions for electromagnetic waves proposed by myself earlier,
the final results was reported in the IMA preprint #1482:
"Absorbing Boundary Conditions for Electromagnetic Wave Propagation."
The second project is to develop efficient parallel numerical
methods based on the domain decomposition (divide-and-conquer)
technique for solving plate bending problems from structure
mechanics. This project has been worked jointly with three
other IMA participants, Petter Bjørstad and Talal Rahman
(University of Bergen, Norway), and Maksymilian Dryja (University
of Warsaw, Poland). In this project we construct and analyze
some so-called Additive Schwarz Methods for the plate bending
problems based on non-overlapping domain decomposition. We
have finished the theoretical analysis of our new methods
and currently we are doing numerical tests to check the efficiency
of the methods. The final resluts of this project will be
written into a joint paper entitled: "Non-overlapping Additive
Schwarz Method for the Biharmomic Equation." Finally, in addition
to working on the above two projects, the IMA support enables
me to have time to make the following my three earlier papers
in their final versions while I was at the IMA. The three
papers are: "Analysis of a Domain Decomposition Method for
the Nearly Elastic Wave Equations Based on Mixed Finite Element
Methods" (IMA preprint #1491); "Formulation and Mathematical
Analysis of a Fluid-Solid Interaction Problem" (IMA preprint
#1495); "Finite Element Methods and Domain Decomposition Algorithms
for a Fluid-Solid Interaction Problem" (IMA preprint #1496).
Once again I like thank you, Professor Friedman and all IMA
people for all your help to me. The three month stay in IMA
was very very memorable for me. I enjoyed every moment while
I was a member of the IMA family. In fact, I am looking forward
to revisit IMA in year 2000.
from the University of Augsburg (Lehrstuhl fur Angew Mathematics)
was a visitor in June'97. His report follows:
My visit at the Institute of Mathematics and its Applications,
University of Minnesota at Minneapolis from June 1 - June
30, 1997 was within the IMA Annual Program "Mathematics in
High Performance Computing. During my stay I participated
in the workshop "Parallel Solution of PDEs" which took part
from June 9 - June 13, 1997. I contributed by a talk entitled
"Adaptive finite element methods for domain decomposition
on nonmatching grids."
That workshop offered the opportunity to intensify already
existing cooperations with colleagues as, for instance, Olof
Widlund (Courant Institute of Mathematical Sciences) and to
initiate new contacts with, e.g., Yvon Maday (Université
Pierre et Marie Curie, Paris) in the area of domain decomposition
on nonmatching grids which is a specific topic in domain
decomposition methods that attracted considerable attention
during the last couple of years. During my stay at the IMA
I prepared two papers: one will appear in the proceedings
of the above mentioned workshop and the other one entitled
"Efficient parallel solution of fully potential flow problems
by domain decomposition methods on nonmatching grids" reflecting
some joint work with the same coauthors over the last two
years is scheduled to appear in the "East-West Journal of
Besides the activities in the field of domain decomposition
methods I had very interesting discussions with Professor
Friedman and Professor Reitich about mathematical modelling
and numerical simulation of electro- and magnetorheological
fluids. The modelling and simulation of electrorheological
fluids and applications in the automobile industry (dampers,
clutches, and mounts) is currently one of the main research
topics in my group. Actually, it is part of an interdisciplinary
national research project (Sonderforschungsbereich 438: Mathematische
Modellierung, Simulation und Verifikation in materialorientierten
Prozessen und intelligenten Systemen [Mathematical modelling,
simulation, and verification in material oriented processes
and intelligent systems]). I will keep in touch with Professors
Friedman and Reitich concerning this issue and hope that they
will have the opportunity to be guests of the "Sonderforschungsbereich"
I would like to take the opportunity to thank you, Professor
Friedman and the staff of the IMA again for the kind hospitality
and for providing me with such excellent working conditions.
I wish you and the IMA all the best for the future and hope
that the contacts that have initiated will result in a fruitful
I think that it was a fascinating and fruitful experience
for me and I also hope that some direct co-operation with
the IMA will result in the area of "Mathematical Modelling
and Numerical Simulation of Electro- and Magnetorheological
Fluids" as already discussed during my stay with Professors
Friedman and Reitich.
from Universität Heidelberg (Institut für Angewandte
Mathematik) was a visitor from May 29 - June 29, 1997. has
the following report:
COMPUTATION OF MULTI-DIMENSIONAL RADIATIVE TRANSFER
The aim of my present work is to provide algorithms and code
for astrophysicists to simulate radiative transfer problems.
Simulation by the linear Boltzmann equation
requires enormous computing resources, memory as well as time.
The monochromous model is five-dimensional for three space
dimensions. The typical data (,
and f in (1)) vary over several orders of magnitude
with concentration to small areas. Accordingly, solutions
may have large gradients in parts of the domain which require
a high resolution to avoid pollution effects.
These "exterior" conditions called for the use of most advanced
solution techniques and I decided for parallelization and
adaptive grid generation. Since the latter relies on Galerkin
discretizations to be efficient and reliable, a finite element
discretization was developed. During my month at the IMA I
had the time and concentration -- away from daily university
business -- to do a thorough stability analysis for this discretization.
The resulting article will soon be ready for publication.
The opportunity to meet other scientists for discussion was
of great value: Endre Süli gave a lot of hints according
to his experience with the streamline diffusion method and
I could talk with Ronald Hoppe about the numerical treatment
of Maxwell's equations, which will be my future field of interest.
I also used the time to port my code to newly available machines,
the T3E and the SGI/Cray Origin 2000.
Finally, the invitation to the IMA gave me the opportunity
to visit the NCSA in Urbana/Champaign and to start a collaboration
on radiative transfer simulation with Mike Norman there.
of the University of Delaware (Mathematics and Science) was
a visitor from February 1 - March 31, 1997. He writes:
While at the IMA in February and March my main activity was
concerned with a problem of uniqueness for scattering by obstacles
in waveguides. The boundary conditions on the wave guide walls
as well on the boundary of the scatterer play a crucial role
in establishing uniqueness. Moreover it is not altogether
obvious how best to incorporate a condition of propagation,
a radiation condition. I spent a lot of time trying to revise
a paper on this subject. It turns out that uniqueness can
be establish for all but a discrete number of frequencies
however we were only able to accomplish this for Dirichlet
conditions on the scatterer and then only by imposing substantial
geometric restrictions. I interacted with many people at the
IMA on this subject including Fadil Santosa,Walter Littman
and Hans Weinberger. After giving a talk on this subject at
the PDE seminar Hans suggested an alternate method of proof
which might help reduce the geometric constraints. I am still
working on this and of course will gratefully cite the IMA
in the forthcoming paper. If this idea with Hans works out
I would hope it will result in another paper. A second area
of activity at the IMA dealt with inverse problems. I had
many stimulating discussions with Frank Natterer and Margaret
Cheney which may result in a collaboration with Margaret.
I also presented a talk on this subject at the post doc seminar.
After my talk in the analysis seminar I had some very interesting
discussions with John Lowengrub on preconditioners for first
kind integral equations on planar boundaries. I described
a method we found which resulted in startling improvement
in the convergence rate of conjugate gradient solutions. John
suggested that a generalization to non-planar surfaces might
be possible using some of his results. I am carrying the papers
he gave me trying to find some time to study them. If this
idea bears fruit it could have significant impact in accelerating
convergence of a large class of first kind integral equations.
I attended the workshop on medical imaging and found it most
illuminating. All in all I found the stay very useful for
me in providing some new ideas and interaction with a large
number of interested and interesting colleagues. I am grateful
for the chance to be there.
of the Czech Academy of Sciences (Decision-making Theory)
ten month stay (September 1996 - June 1997) with the IMA was
supported by the Fulbright fellowship and by the IMA. During
that time I defended my Ph.D. thesis  and have been working
on several projects.
I finished the final version of my paper  which has already
been accepted for publication in the SIAM Journal on Numerical
Analysis. This paper was also published as the IMA preprint
No. 1485. The paper deals with numerical solutions to two-dimensional
problems in nonlinear elasticity when the stored energy density
of a material attains its minimum on two mutually different
rotationally invariant sets (e.g. two crystallographic states
- phases of the material). In many cases gradients of elements
of minimizing sequences oscillate between these two sets.
The alternation of these phases makes a microstructure. The
oscillations cause the energy functional being not weakly
lower semicontinuous and its minimum is not generally attained.
Therefore, some kind of relaxation is needed. We use relaxation
based on Young measures representation.
second paper written during my stay in the IMA is . This
paper is devoted to investigation of geometric properties
of sets of (generalized) Young functionals. Roughly speaking,
taking a bounded sequence ,
and bounded we define the Young functional
as (after possible extraction of a subsequence) ,
a separable subspace of the space of Carathéodory functions.
Of course, the set of Young functionals depends on how large
we take the subspace H. Under certain assumptions it
can be shown that this set is convex and -compact;
cf. . In the paper we study geometric properties of these
sets, especially, rays, extreme points and extreme rays. Applications
to optimal control problems and the Choquet theory are given.
The third paper  which has appeared as the IMA preprint
No. 1494 studies a relation between a special kind of Young
functionals called DiPerna-Majda measures and uniform integrability
of L1-bounded sequences. We apply our results
to Fatou's lemma and study when the weak convergence in Lp
implies the strong one.
Further, I have been working on three ongoing papers. The
first one is devoted to studying of a finite element approximation
of the DiPerna-Majda measures . Especially, we are about
to establish results concerning convergence and error estimates.
Further, we will apply our methods to examples from the optimal
In the second paper  we numerically solve tasks appearing
in micromagnetics. Mathematically, the problem reduces to
minimization of not weakly lower semicontinuous integral functional
and to its relaxation.
The last ongoing paper  (together with M. Luskin) contains
three-dimensional problems solved in  in two dimensions.
I had discussions (but without common papers) especially with
V. Sverak, S. Mueller, T. Iwaniec, P. Plechac and also with
A. Prohl and M. Gobbert.
M. Kruzík: Oscillations, Concentrations and Microstructure
Modeling., Ph.D. thesis, Charles University, Prague, 1996.
M. Kruzík: Numerical approach to double well problems.,
M. Kruzík, T. Roubícek: Geometric properties
of generalized Young functionals., submitted.
M. Kruzík: DiPerna-Majda measures and uniform integrability.,
M. Kruzík, T. Roubícek, M. Vítková:
Optimal control problems admitting concentrations and oscillations
effects and their numerical treatment., in preparation.
M. Kruzík: Numerical solution to relaxed problems in
micromagnetics., in preparation.
M. Kruzík, M. Luskin: Numerical solutions to three-dimensional
double well problems., in preparation.
T. Roubícek: Relaxation in Optimization Theory and
Variational Calculus., W. de Gruyter, Berlin, 1997.
of Indiana University/Purdue University IUPUI(Mathematical
Thank you for the opportunity to be in residence for two months
during the past academic year. The stay at the IMA, during
the months of September and April, was a crucial part of my
sabbatical leave from IUPUI during this past year.
Here is a brief summary of my activities at the IMA, which
I hope will be useful for your records as well as my own:
I was in residence at the IMA for Sept. 1 - Sept. 30 in 1996
and April 1 - April 30 in 1997. That period afforded an excellent
opportunity for me to work intensively on my research, which
at present has to do with nonlinear wave equations (e.g.,
nonlinear complexvalued Klein-Gordon equations and related
systems). The IMA's computer facilities and the University's
library facilities were both very useful in this regard.
During my stay in September, 1996, I also attended the tutorials
on Message Passing Interface (MPI) and High Performance Fortran
(HPF) (Sept. 9-20) as well as the workshop on Algorithms for
Parallel Processing (Sept. 16-20). I found the work with MPI
(with Rusty Lusk and Bill Gropp) particularly informative.
In my work during the rest of the month, discussions with
Matthias Gobbert and Qing Nie were very helpful.
During the PDE Software workshop that I attended in April
(April 21-25, 1997) I interacted especially with Olivier Pironneau,
Petter Bjørstad, and Klaus Johannsen. At other times
during the month of April, I had extensive talks with Xiaobing
Feng and Martin Kruzik.
A special objective completed during my sabbatical was to
have some discussions with Fadil Santosa, so as to learn more
about the Minnesota Center for Industrial Mathematics (MCIM).
Based on those discussions I will be able to act as a resource
person in the event that a somewhat similar program is initiated
in the Indianapolis area at some time in the future.
In addition it was especially enjoyable to have the opportunity
to renew my acquaintance with a number of people after many
years, in particular, with David Sattinger, Walter Littman,
Peter Rejto, George Sell, and Hans Weinberger.
Thanks again for making my stay so productive and enjoyable.
I want to thank you again for the invitation to participate
in the conference this past weekend. All of the honorees except
for Willard were at Minnesota when I was a student, and Willard
came just as I left. So I greatly appreciated the opportunity
to honor their long and distinguished careers. And, of course,
it was a special pleasure to honor Han's career.
from Christian-Albrechts Universität Kiel (Mathematisches
Seminar II) reports:
The primary goal of my stay at the IMA of the University of
Minnesota during the academic year August 1, '96 - July 31,
'97 was to get acquainted with the modeling and analysis of
martensite crystals exhibiting microstructure, with emphasis
on numerical methods. This project was supported by the german
research association (DFG) through a scholarship.
I gratefully acknowledge the support granted by Prof. M. Luskin
from the School of Mathematics (University of Minnesota) who
introduced me to this field and focused my attention on relevant
literature, current talks or courses, like the course offered
by Prof. James (Department of Aerospace Engineering and Mechanics)
during the winter quarter 96/97, dealing with martensite crystals
and the physical as well as mathematical background.
In particular, I read articles of the authors B. Li, C. Collins,
P. Gremaud, D. Kinderlehrer, P. Kloucek and M. Luskin that
have been published throughout the last decade (see  for
references), dealing with the approximation of (simply laminated)
microstructures. These authors propose and analyze conforming
and nonconforming finite element models to compute microstructures
through finite dimensional models. It is well-known, that
these numerical methods perform well in the context of minimizing
But, if we are concerned with the minimization of nonconvex
functionals on a given set as it is the case here for the
Ericksen-James energy density allowing microstructure, we
need the triangulation of the domain to be aligned to the
laminates in order to be able to numerically resolve the microstructure.
This is clearly seen in computational experiments and is reflected
by the fact that the related numerical analysis gives suboptimal
rates of convergence for quantities of interest in this context.
The conclusion from this is that the standard finite element
methods enforce too many constraints of continuity to the
computed solution, thus polluting it with (non-aligned) mesh
information. This was the starting point of Dr. M. Gobbert
(Postdoc at the IMA during the same period of time) and me
to propose new numerical ansatzes that are more flexible,
thus being capable to resolve microstructure in the case of
acting forces or for evolutionary models.
In our joint work, we proposed a new finite element method,
based on discontinuous elements, in order to increase
the flexibility of the approximation for general triangulations
of the domain. The (weakened) continuity constraint of the
computed deformation is taken into account through a penalty
term added to the bulk energy. In the same sense, the prescription
of the given boundary data is relaxed to avoid pollution effects
on the approximation coming from the averaged boundary data.
Despite of the short time, we succeeded in obtaining the following
of a new finite element method suitable for resolving
simply laminated microstructure on general grid topologies,
of a mathematical convergence analysis, qualifying
the approximation of several quantities describing microstructure.
We emphasize that we obtained results of convergence that
are better by a factor of 4 compared to those obtained
by the previously named authors,
Experiments - based on the finite-element package FEAT2D
-- have been performed. In particular, they show the superiority
of this ansatz in comparison with 'classical' (non-)conforming
methods. The resolution of microstructure is highly independent
on the underlying mesh.
We are now preparing publication of these results, see 
and . It is further intended to extend our collaboration
to test this new algorithm for evolutionary models, e.g.,
describing movement of interfaces between different phases.
A second subject of research was the construction of time-splitting
schemes for computing chemically reacting flows. This project
is part of a collaboration with Prof. Sell (School of Mathematics
of the University of Minnesota) and his student D. Norman.
I proposed and analyzed first and second order time-discretization
schemes that allow computation of velocity, temperature, and
species in a decoupled manner without loosing accuracy, ,
. These new ansatzes give way to parallelization ansatzes
to effectively compute chemically reacting flows in a reliable
way. In these studies, I assume homogeneous Dirichlet type
boundary data, and it is intended in the ongoing collaboration
with Prof. Sell and D. Norman to construct numerical models
applicable to cases with physically more relevant boundary
The latter project is closely related to fluid flows governed
by the incompressible Navier-Stokes equations, where I worked
on time-discretization schemes (projection methods) during
my Ph.D. studies in Heidelberg. During my stay at the IMA,
I finished a monograph on this topic that is recently published,
Finally, I would like to thank the IMA for the hospitality
during my stay there. I enjoyed the nice and stimulating atmosphere:
the broad range of workshops was a very good opportunity for
me to get introduced to new topics and the acquaintance with
researchers in various fields of (numerical) analysis gave
me the chance of further collaboration.
Matthias Gobbert and Andreas Prohl, On a new finite element
method for solving a multi-well problem, in preparation
Matthias Gobbert and Andreas Prohl, A comparison of classical
and new methods for approximating laminated microstructure,
Mitchell Luskin, On the computation of crystalline microstructure,
Acta Numerica (1996).
Andreas Prohl, Projection and Quasi-Compressibility Methods
for Solving the Incompressible Navier-Stokes Equations,
Andreas Prohl, An adaptive method for computing laminated
microstructure, in preparation
Andreas Prohl, Proposal and analysis of a first-order
projection-based time-splitting scheme for solving a model
for chemically reacting flows, in preparation
Andreas Prohl, Proposal and analysis of a second-order
projection-based time-splitting scheme for solving a model
for chemically reacting flows, in preparation
from the University of Heidelberg (fur Angewandte Mathematik)
during his April - June 1997 visit gave a presentation on
Special Short Course: Computational Methods for the Incompressible
Navier-Stokes Equations held on April 14-15, May 5-6, 1997.
He also delivered a lecture on the following workshops: "Grid
Generation and Adaptive Algorithms, April 28 - May 2, 1997
and "Parallel Methods for Partial Differential Equations,"
June 9-13, 1997; Below is his a research report:
The area of my current research is the efficient numerical
solution of partial differential equations. Topics of particular
1. Adaptive Finite Element Methods: A general concept for
a posteriori error estimation and adaptive mesh design has
been developed which is applicable to almost any problem posed
in variational form and yields control for arbitrary functionals
of the error. The potential of this approach is currently
investigated for various problems in computational science,
e.g., fluid mechanics, hyperbolic conservation laws, elasticity
and elasto-plasticity, radiative transfer, reactive flows,
dynamical systems, shape optimization.
Lecture "A general concept for adaptivity in finite element
methods" (IMA Workshop on Grid Generation and Adaptive Algorithms,
April 28 - May 2, 1997)
Report "A general concept of adaptivity in finite element
methods with applications to problems in fluid and structural
mechanics" (with R. Becker, Proc. IMA Workshop on Grid Generation
and Adaptive Algorithms, April 28 - May 2, 1997)
Lecture "How to control the error in the numerical approximation
of PDE" (Colloquium, School of Mathematics, University of
Minnesota, April 17, 1997)
Current project "A posteriori error control and mesh adaptation
for FE models in elasticity and elasto plasticity" (with
F.-T. Suttmeier, University of Heidelberg)
New project "A posteriori error control and mesh optimization
in the h-p finite element method" (with R. L. Scott, Visitor/Organization
2. Domain-Decomposition and Parallel Multigrid Methods: Large
scale simulations particularly in fluid mechanics require
the use of parallel computers. It is investigated how the
recently developed highly efficient sequential multigrid solvers
for the Navier-Stokes equations can be implemented on distributed
memory machines. The goal is to find the best compromise between
the concept of domain-decomposition on the discretization
level and simple grid-decomposition on the algebra level.
Lecture "A parallel multigrid solver for the incompressible
Navier-Stokes equations" (IMA Workshop on Parallel Methods
for Partial Differential Equations, June 9-13, 1997)
Report "Parallel solution of the incompressible Navier-Stokes
equations by domain decomposition and multigrid methods"
(Proc. IMA Workshop on Parallel Methods for Partial Differential
Equations, June 9-13, 1997)
3. Incompressible Navier-Stokes Equations:The numerical simulation
of the incompressible Navier-Stokes equations on complex geometries
requires highly robust and efficient methods. Recently such
methods have been devised by combining the flexibility of
finite element discretizations with the efficiency of multigrid
Lecture Series on "Computational Methods for the incompressible
Navier-Stokes Equations" Part I: Discrete models Part II:
Multigrid solution Part III: A priori error analysis Part
IV: Adaptive methods
IMA Short Course, April 14, 15, May 5, 6, 1997)
Current project "An analysis of Chorin's projection method
for the incompressible Navier-Stokes equations" (with A.
Prohl, Postdoc at the IMA)
4. Transport-Dominated Problems: The reliable numerical solution
of transport-dominated equations poses new problems. There
are significant far-field effects in the error propagation
which cannot be captured by the usual local error estimators.
The discretization by the finite element Galerkin method with
streamline diffusion stabilization opens the way for rigorously
based adaptive error control by means of global "duality arguments."
- Current project "An adaptive streamline-diffusion finite
element method for hyperbolic conservation laws" (with Chr.
Führer, University of Heidelberg)
New project "A posteriori error analysis of the streamline
diffusion finite element method" (with E. Suli, Visitor
Thanks again for this pleasant time at the IMA.
of the University of Arizona State University (Mathematics)
was a visitor from May 11 - June 14, 1997. He attended the
workshop on "Parallel Solution of PDE" held on June 9 - 13,
1997. She writes:
I am not convinced that my contributions are immediately very
stunning. For myself the contacts I developed, although not
immediately collaborative, have led to several new directions
for both of the research projects I was involved in. In particular
the workshop on finite elements has broader impact on my general
research activities. I expect that I will take some discussions
on additive Schwarz methods into a draft of another paper,
which I will then send to some of the other participants.
At that point some collaborations I hope the collaborations
I think you know also that I had a severe distraction from
ASU during my time at IMA. I want to thank you though for
the opportunity to be at the IMA. Even with the distraction
of ASU via email, I was able to make some substantial progress
in my own research.
Thanks again for the hospitality shown by all the staff of
Methods for Third Order Partial Differential Equations
Partial differential equations containing terms that are third
order spatial derivatives arise in the modeling of many practical
situations involving wave propagation in nonlinear dispersive
media. One well-known and well-studied example is the Korteweg-de
Vries equation which accounts for dissipative effects in addition
to non-linearity and dispersion. Numerical solutions of such
equations must accurately predict all dissipative, dispersive
and nonlinear effects of the wave propagation. The design
of suitable solvers is therefore not straightforward.
My research has focused on the use of pseudospectral methods
for the solution of equations with third order derivatives
in space on non-periodic domains. Pseudospectral methods offer
the advantage of high accuracy, in fact spectral accuracy,
if the underlying approximations are of sufficiently high
order. Previous approaches have considered the use of either
i) approximations based on Fourier expansions of the wave
on a periodic domain or ii) finite difference approaches for
non-periodic domains. The former approach has the clear disadvantage
of requiring periodicity, which is not always realistic physically,
and hence leads to the use of numerical domains which are
artificially large with respect to the physical domain under
consideration. In the latter case the design of schemes which
are both of high accuracy and allow for adequate representation
of boundary conditions and nonlinear effects is cumbersome.
To obtain approximations of high order to third-order derivatives
the stencils needed are not compact, which requires that sets
of stencils are required to model the regions near boundaries.
Moreover, high accuracy with respect to local error control
does not ensure minimal artificial dispersion and dissipation
of the method.
Pseudospectral methods offer the advantage of globality and
spectral accuracy, and hence avoid the aforementioned problems.
On the other hand the resulting operators are notoriously
ill conditioned with respect to stability and are computationally
intensive with respect to advancement in time.
During my visit to the IMA I was able to complete my study
of the use of a modified approach in pseudospectral methods
for solution of equations with third order derivatives. The
methods developed were compared with standard finite difference
and periodic pseudospectral methods. Results demonstrate the
effectiveness of the approach and are described in the first
listed paper below. The research was enhanced by the short
term visit of Jerry Bona to the IMA. Jerry presented some
thought-provoking results of his research in this area at
one of the weekly seminars.
Methods for Solution of Least Squares Problems
other portion of my time at the IMA was spent studying domain
decomposition approaches for the solution of over-determined
sets of linear equations. Parallel solution of large-scale
problems can be achieved by the application of decomposition
in space. The approach follows ideas adopted in recent years
for finite-element solution of elliptic equations by additive
During my visit I presented this work at the IMA postdoctoral
seminar. Because of the anticipated audience I concentrated
on the connections between the multisplitting methods, which
have been proposed for linear systems, with additive schwarz
techniques. The reformulation of development of not only the
multisplitting approach, but also of additive Schwarz for
finite-element problems. One of the drawbacks of the domain
decomposition approach is the effective incorporation of coupling
effects between subdomains. In multisplitting a secondary
iterative stage has been incorporated to couple the information
from local solutions, hence facilitating the faster solution
of the global solution. Although no collaborative work has
yet arisen out of this discussion the resulting discussions
were very helpful and it is still possible that some collaborations
could arise if the initial research is promising. Some of
this research is described in the second report listed.
Renaut , "Evaluation of Chebychev Pseudospectral Methods
for Third-Order Differential Equations." Numerical Algorithms,
Frommer and R. A. Renaut, "Parallel Subspace Decomposition
Methods for Quadratic Functionals," in preparation.
from Brown University (Applied Mathematics) was a visitor
from April 1 - June 30, 1997.
Here is my report for the IMA visit.
I have enjoyed my IMA visit very much. Thank you for all the
Joint research with Professor Bernardo Cockburn, who is also
an IMA visitor, on discontinuous Galerkin method for convection
dominated problems has been performed. Discontinuous Galerkin
method combines the advantages of finite element methods in
treating complicated geometry and of finite difference methods
in non-oscillatory high resolution for shocks. The progress
during my visit is two-fold:
have studied the Local Discontinuous Galerkin methods for
nonlinear, time-dependent convection-diffusion systems.
These methods are an extension of the Runge-Kutta Discontinuous
Galerkin methods for purely hyperbolic systems to convection-diffusion
systems and share with those methods their high parallelizability,
their high-order formal accuracy, and their easy handling
of complicated geometries, for convection dominated problems.
It is proven that for scalar equations, the Local Discontinuous
Galerkin methods are L2-stable in the
nonlinear case. Moreover, in the linear case, it is shown
that if polynomials of degree k are used, the methods
are k-th order accurate for general triangulations;
although this order of convergence is suboptimal, it is
sharp for the LDG methods. Preliminary numerical examples
displaying the performance of the method are shown.
have extended the method to multidimensional nonlinear systems
of conservation laws. The algorithms are described and discussed,
including algorithm formulation and practical implementation
issues such as the numerical fluxes, quadrature rules, degrees
of freedom, and the slope limiters, both in the triangular
and the rectangular element cases. Numerical experiments
for two dimensional Euler equations of compressible gas
dynamics are presented that show the effect of the (formal)
order of accuracy and the use of triangles or rectangles,
on the quality of the approximation.
following two IMA preprints summarize the results:
Cockburn and C.-W. Shu, The local discontinuous Galerkin
method for time-dependent convection-diffusion systems,
IMA Preprint 1478. Submitted to SIAM Journal on Numerical
Cockburn and C.-W. Shu, The Runge-Kutta discontinuous Galerkin
method for conservation laws V: multidimensional systems,
IMA Preprint 1492. Submitted to Journal of Computational
Joint research with Professors Bernardo Cockburn and Endre
Suli (both are IMA visitors) about accuracy enhancements for
discontinuous Galerkin methods is also initiated and is still
from University of California, San Diego (Electrical and Computer
Engineering) was a visitor from November 10 - 15, 1997. He
Thank you very much for arranging for my participation in
the recent IMA Workshop on the Mathematics of Information
Coding, Extraction, and Distribution. The meeting provided
a nice opportunity to hear about an unusually broad range
of technical activities, and to interact informally with a
wonderful group of researchers. Thanks, also, to you and the
IMA staff for providing the comfortable office, convenient
(and user-friendly!) computing facilities, useful local information,
enjoyable social functions, and the generous travel support.
the University of Minnesota (Mathematics) reports on his activities
at the IMA during academic year 1996-1997:
During the 1996-1997 program my activities mostly concentrated
on the following areas:
using computational methods to attack certain open problems
in the Calculus of Variations and harmonic analysis (in
collaboration with P. Plechac, an IMA visitor, and also
Tadeusz Iwaniec, and Stefan Muller, short-term IMA visitors)
(or at least providing some guidance to) Martin Kruzik,
a Sloan Fellow, who stayed at the IMA for most of the year
learning about recent advances in CFM (computational fluid
mechanics) from the world's leading experts who visited
the IMA during the year (R. Rannacher, O. Pirroneau)
I will now expand on (1): this work mostly concentrated on
trying to obtain a "computational" answer to the long-standing
open question whether rank-one convexity implies quasi-convexity
for function on two by two matrices. Recently there has been
a new surge of interest in this question, since it turned
out that it is closely related to the problem of the best
constants in the Lp estimates for the complex
Hilbert transformation. Together with Plechac, we tried a
new computational approach to answer this question. Pleachac
wrote the codes and by now the calculations has been going
on for about 9 months. So far the evidence we gathered supports
the conjectures. There is several numerical problems one encounters
in the calculation. The most difficult is the following: Given
a smooth function f on two by two matrices, how can we compute
its rank-one convex envelope Rf (which is the sup of all rank-one
convex function which are less or equal to f)? This problem
seems to be interesting not only from the numerical point
of view, but also from the point of view of general computability
Plechac and I will write a joint paper explaining our approach
and our conclusions.
of West Group of West Publishing Company (Research) reports:
On 18-20 November 1996, I attended the workshop "Data Mining
and Industrial Applications" put on by the Institute for Mathematics
and its Applications at the University of Minnesota. I found
this workshop to be very useful. It provided the opportunity
of hearing many of the leading researchers in the new field
of data mining present their research in an informal setting.
Unlike at a large conference, it was easy to meet and talk
at length with the speakers and other participants. The quality
of the presentations was very high. The connections of the
new field of data mining to other more mature disciplines
such as statistics, pattern recognition, and machine learning
was made clear.
My own research interests are in automatic text classification.
I had the opportunity of meeting for the first time researchers
whose work I had followed in this area. Since the conference,
I have continued to have e-mail exchanges with some of the
other participants. I am looking forward to meeting with the
participants at future conferences and will monitor the literature
as new research developments and subsequent commercial products
Data mining is currently a very popular field receiving much
attention. The workshop did a good job of stimulating my thinking
about this field and its ties to the related discipline mentioned
above. Should my company decide to pursue research or development
in data mining, my having attended the workshop will give
us a good starting point.
I found the workshop to be very worthwhile and would be interested
in participating in similar workshops in the future. Thank
you again for IMA's invitation for me to participate.
from Department of Mathematics and Statistics, University
of Maryland, Baltimore County reports:
I spent the academic year 1996/97 at the IMA as part of the
special year in High-Performance Computing.
During this year, I participated in many of the workshops
and tutorials held at the institute, in particular the ones
relating to numerical methods for partial differential equations
and their efficient implementation on modern computers. Besides
I participated actively in the Post-Doc Seminar. Outside the
IMA, I participated actively in the Numerical Analysis seminar,
in which I gave a talk on "A Homogenization Technique for
the Development of Mesoscopic Scale Models for Chemical Vapor
Deposition," as well as the Matlab seminar in the Winter quarter
1997, in which I also gave two talks.
Besides this participation, I continued my dissertation research
with collaborators at Arizona State University and Motorola
(Mesa, Arizona). To this end, I spent three weeks at Motorola
working on extending our results to other physical processes.
A paper about the work done in collaboration with Motorola
and Arizona State University was published in the Journal
of the Electrochemical Society: Matthias K. Gobbert, Tushar
P. Merchant, Leonard J. Borucki, and Timothy S. Cale, "A Multiscale
Simulator for Chemical Vapor Deposition," J. Electrochem.
Soc., vol. 144, no. 11, 1997, pp. 3945-3951.
In addition to continuing my dissertation research, a new
project on the computation of crystalline microstructure was
begun in collaboration with the long-term visitor Andreas
Prohl from the University of Heidelberg (Germany), now at
the University of Kiel (Germany). This is work inspired by
earlier results of Mitchell Luskin of the School of Mathematics
at the University of Minnesota. The problem is the discretization
and minimization of a non-convex energy functional arising
from modeling the elastic energy of phase transformations
in shape-memory alloys, a topic of considerable and growing
practical importance. We succeeded in improving the old energy
estimates for classical conforming and non-conforming elements
(half order in the mesh parameter) by using discontinuous
finite elements (second order in the mesh parameter) and a
scaled energy functional. This result was both proven by theoretical
analyses and demonstrated by numerical calculations for an
extensive case study on a test problem. This collaboration
represents a great example for the type of collaboration arising
in the interdisciplinary environment of the IMA. The Two papers
below reports on the theoretical analyses and the numerical
case study, respectively, are currently still under preparation
and will be submitted for publication in the IMA Preprint
Matthias K. Gobbert and Andreas Prohl, On Finite Element
Methods for Solving a Multi-Well Problem.
Matthias K. Gobbert and Andreas Prohl, A Comparison of Classical
and New Finite Elements for the Computation of Crystalline
of the University of Alberta, Department of Mathematical Sciences
Industrial Fellowship with Lockheed Martin
I, Michael A. Kouritzin, was fortunate to spend two productive
years at the Institute for Mathematics and its Applications.
I will always be very grateful to the IMA staff and the personnel
at Lockheed Martin Tactical Defense Systems whom I interacted
with. Before coming to Minnesota, I had a reasonable background
in stochastic convergence and some aspects of applied mathematics
as well as a developing interest in parabolic equations. I
was asked by my industrial partner to investigate applying
non-linear filtering theory to air traffic management and
defense industry problems. I was neither familiar with the
theory of non-linear filtering nor their modeling
and implementation ideas. However, after this became understood
by Lockheed, they allowed me the time to learn and the opportunity
to develop my own ideas. I suggested several modeling ideas
some of which were incorporated into proposals and, more importantly,
developed and promoted a practical method of non-linear filtering.
The traditional mathematical solutions to the non-linear filtering
problem under classical conditions neither are readily convenient
for implementation nor apply to the problems which were of
interest. Indeed, there is no single best practical method
of filtering for nonlinear problems where the Kalman filter
does not apply.
My first approach, developed under the encouragement of Avner
Friedman, Craig Poling, Brian Leininger, Ron Mahler, and Keith
Kastella, was to try to reduce the filtering problem down
to the easily implementable problem of convolution (plus certain
transformations, scaling etc.). The first subproblem with
this approach was to examine the class of problems that could
be exactly implemented as a single convolution. In two papers
"On exact filters for ..." and "A nonlinear filter for ...",
written while at the IMA and listed below, we introduced and
studied this concept of exact infinite dimensional filters.
Later, near the end of my tenure at the IMA, I discovered
additional classes of problems which can be solved as exact
infinite dimensional filters. These classes are currently
being written into an additional paper. There turned out to
be a second interesting subproblem: What type of filtering
problems could be approximately solved with a modest
number of convolutions? This question lead to some interesting
mathematical developments which are also being written up
into two papers. Overall, these convolution-based methods
performed extremely well in tests, have many inherent advantages,
and have gained the support of Lockheed Martin. I also became
interested in the branching particle system approach to nonlinear
filtering suggested by Dan Crisan and Terry Lyons as well
as in the multiple-target filtering problems. Lockheed Martin
and myself have agreed to continue collaborating in all these
filtering efforts. I am indebted to Professors Avner Friedman,
Walter Littman, and Robert Gulliver for their guidance and
assistance with these problems.
My other major area of interest while at the IMA was averaging
and stochastic averaging for arbitrary-order parabolic equations
with random coefficients. I am pleased to acknowledge benefit
from discussions with Professors George Sell and Avner Friedman
at Minnesota. I wrote four papers in this area while at the
IMA and three of them have already been accepted. Furthermore,
I also worked on related problems in stochastic partial differential
equations which I hope to be able to complete and publish.
D. Dawson and M. A. Kouritzin. Invariance principles for parabolic
equations with random coefficients. J. Functional Analysis,
149:377-414, 1997. IMA Preprint #1433.
M.A. Kouritzin. Averaging for fundamental solutions of parabolic
equations. J. Differential Equations,
136:35-75, 1997. IMA Preprint #1379.
M.A. Kouritzin. Approximations for higher order parabolic
equations. Submitted. IMA Preprint #1444.
M.A. Kouritzin, "Stochastic processes and perturbation problems
defined by parabolic equations with a small parameter," to
appear in The Second World Congress of Non-linear Analysts.
IMA Preprint #1443.
M.A. Kouritzin, "On exact filters for continuous signals with
discrete observations", to appear in the IEEE Transactions
on Automatic Control. IMA Preprint #1409.
M.A. Kouritzin, "Arbitrary order parabolic stochastic partial
differential equations with general Hilbert-space-valued noise",
The IMS Bulletin 26 (1997) pp. 322-323.
K. Kastella, M.A. Kouritzin, and A. Zatezalo, "A nonlinear
filter for altitude tracking", October 1996 Proceedings
of the Air Traffic Control Association pp. 1-5.
of Massachusetts Institute of Technology (Mathematics)
I. Research. My research during the year was in three
areas: nonlinear filtering of diffusion processes, parameter
estimation for stochastic parabolic equations, and analytical
theory of boundary value problems for stochastic partial differential
Nonlinear filtering. The problem in question is estimation
of the unobserved component of a partially observed system.
This problem arises in many applications (navigation, target
The unobserved process (signal) is modeled by a nonlinear
diffusion equation, and the observations, by a nonlinear transform
of the signal, corrupted by noise. Both continuous and discrete
time observations are possible. The objective is to develop
a numerical algorithm for efficient real time computation
of the approximation of the optimal nonlinear filter. The
central idea of the algorithm is to separate the deterministic
and stochastic information. By performing off line the computations
involving only deterministic information, the on-line performance
of the algorithm can be significantly improved. Theoretical
issues include the proof of convergence of the approximate
filter and the analysis of the complexity of the resulting
The following papers were prepared:
S. Lototsky and B. L. Rozovskii. Recursive Nonlinear Filter
for a Continuous - Discrete Time Model: Separation of Parameters
and Observations, IEEE Transactions on Automatic Control
(1998, to appear).
C. P. Fung and S. Lototsky. Nonlinear Filtering: Separation
of Parameters and Observations Using Galerkin Approximation
and Wiener Chaos Decomposition, IMA Preprint Series # 1458,
The first paper deals with the discrete time observations,
while the second paper considers continuous time model.
The results of the investigation were presented at the Workshop
on Stochastic Control and Nonlinear Filtering, North Carolina
State University, October 11 and 12, 1996.
I also had several fruitful discussions about practical implementation
of the algorithm with A. Zatezalo, graduate student at the
School of Mathematics, University of Minnesota, Dr. M. Kouritzin,
IMA postdoc, and with the representatives of the Lockheed
A discussion with Professor P. Bjørstad helped in the
analysis of the complexity of the algorithm.
An interesting idea for the future research -- to use evolutionary
programming for generating the coefficients of the optimal
filter -- was inspired by the talks at the IMA Workshop on
2. Parameter Estimation. The objective is to develop a
method of estimating unknown parameters from the observations
of a random field. One possible application is estimation
of the thermodiffusivity and the cooling coefficient in the
heat balance equation of physical oceanography.
The mathematical model of the observations is a stochastic
evolution equation driven by space-time white noise on a compact
smooth manifold. The unknown parameters appear as the coefficients
of the (known) partial differential operators in the equation.
The novelty of the approach is that no assumptions are made
about the spectral properties of the operators.
An estimate based on finite dimensional projections of the
observations was suggested and the asymptotic properties of
the estimate were studied as the dimension of those projections
was increased. Conditions were found for consistency, asymptotic
normality, and moment convergence of the estimate. Two papers
S. Lototsky and B. L. Rozovskii. Parameter Estimation for Stochastic
Evolution Equations with Non-commuting Operators. IMA Preprint
Series # 1501, August 1997.
S. Lototsky. Parameter Estimation for Stochastic Parabolic Equations:
Asymptotic Properties of a Two-Dimensional Projection Based
Estimate. IMA Preprint Series # 1486, June 1997.
The first paper gives a detailed treatment of the single parameter
case, and the second paper extends some of the results to
the multi-parameter setting.
The content of the first paper was presented in February 1997
at the School of Mathematics Probability Seminar.
Boundary value problems for SPDEs. This research was in
collaboration with Professor N. V. Krylov from the University
of Minnesota School of Mathematics. The objective was to establish
existence, uniqueness, and the regularity of the solution
of the first boundary value problem for SPDEs, without using
compatibility conditions. At this point, the research was
purely theoretical, although possible applications include
optimal nonlinear filtering in a bounded domain and populational
By introducing a special scale of Banach spaces that allow
the derivatives of the functions to blow near the boundary,
we proved, in the case of one spatial variable, the solvability
of the equation in that scale, and determined the maximal
possible rate of explosion of the derivative. A paper was
prepared, describing the results:
N. V. Krylov and S. V. Lototsky. A Sobolev Space Theory of SPDEs
with Constant Coefficients on a Half Line. SIAM Journal on Mathematical
The content of the paper was presented at the MSRI Workshop
on Stochastic Partial Differential Equations, Berkeley, CA,
September 15-19, 1997. The collaboration with Professor N.
V. Krylov continues after I left the IMA, and we are currently
working on extending the results to equations in multi-dimensional
Other Activities. I enjoyed the IMA tutorials on MPI/HPF,
Mathematics of Medical Imaging, and PDE Software, even though
the topics were not directly connected with my research. I
also found interesting the talks at the School of Mathematics
Probability Seminar, and some talks at the PDE, Analysis,
Numerical Analysis, and IMA Postdoc Seminars, and the Colloquium.
During the school year, I was sitting in three classes: Parallel
and High Performance Computing (Fall 1996, Professor V. Kumar),
Malliavin Calculus (Winter 1997, Professor V. Bogachev), Controlled
Diffusion Processes (Spring 1997, Professor N. V. Krylov).
Even though not directly connected with the ares of my current
research, these courses had a great educational value.
who is currently affiliated at Medtronic, Inc. was one of
the postdocs for the 1996-1997 program on "Mathematics of
High-Performance Computing." Below are his activities:
Non-linear Dispersive Equations
In collaboration with Peter Olver and Yi Li from the University
of Minnesota Mathematics Department, we simulated and studied
non-linear dispersive equations in one dimension. I wrote
a general code and supporting software for solving equations
of the form
using very high-order accurate finite differences in space
and a robust trapezoid method (modified for the nonlinear
equation) in time.
After testing the method extensively using exact solutions
and other numerical solutions for this general equation, we
began using the code on the critical surface tension model
developed a method for numerically computing solitary wave
solutions in 1D, by starting with a solution that is close
to a solitary wave solution and selectively damping dispersed
waves in the domain of computation. This method allowed us
to obtain two solitary wave solutions for a collision study.
In an IMA Preprint, we proved the feasibility of this method
for obtaining solitary wave solutions, and showed that to
very high accuracies that the solutions obtained have constant
propagation speeds and constant wave forms. For the critical
surface tension model, we presented a collision solution which
shows the level of dispersion induced by the collision. The
Figures 1 and 2 show the scale between the full waves and
the dispersive waves.
Figure 1: Waves after collision.
Figure 2:Dispersion from collision.
A Posteriori Error Analysis for Hyperbolic Equations
project, a collaboration with Bernardo Cockburn in the University
of Minnesota Department of Mathematics, aimed at completing
a new method for a posteriori error estimates of a
general hyperbolic equation. Cockburn has shown for the
if u(x,t) is an approximate solution with residual
R(u), then the error norm ||v-u|| satisfies
aim was to derive from this equality an a posteriori
error bound not requiring v on the right hand side,
then use numerical means to compute it.
Unfortunately, we found this formulation to not be feasible
in conjunction with using numerical means to compute it. The
computation of estimate is itself is incurring numerical error
that is difficult to eliminate. The terms in the formulation
must largely cancel out, and the time integration of the whole
must be extremely accurate. These error of the estimator grows
exponentially in time and quickly overtake the numerical of
u. This problem is absent in elliptic equations, because
no time variable exists.
fall term postdoc seminars
article entitled "On Comparisons of Time-Domain Scattering
Schemes", a critique of methods of comparing numerical
methods. The article addressed the shortcomings of current
methods and proposed comparison criteria that can be used
to assess fairly the differences in efficiency between two
different numerical methods.
paper entitled "Solitary Waves in the Critical Surface Tension
a poster on the upwind-leapfrog method for electromagnetic
and acoustic scattering predictions at the University of
Michigan, Godunov Seminar.
Cockburn. Personal Communication, 1996.
A. Li, Brian T. Nguyen, and Peter J. Olver. Solitary waves
in the critical surface tension model. Will appear in the
IMA Preprint Series, February, 1998. Submitted to a special
issue of J. Engineering Math, on "Applications of Solitons
and Symmetries," M. Ablowitz& P. Clarkson (eds).
Brian T. Nguyen. On comparisons of time-domain scattering
schemes. IEEE Antennas and Propagation Magazine,
39(1):99-102, February 1997.
of Oracle Corporation reports:
As a Post Doctoral Researcher for the program "Mathematics
in High Performance Computing, 1996-1997" at IMA, I mainly
concentrated on performance issues of Relational Databases
and extended it to various applications like internet, data
mining, data warehousing, etc. The workshops of my interest
were: "High Performance Fortran (HPF);" "The Message Passing
Interface Standard (MPI);" "Algorithms on parallel Processing;"
"Data Mining and Industrial Applications;" "Mathematics on
Information Coding, Extraction and Distribution," etc. During
my stay at IMA, I was able to meet several visitors and other
IMA postdocs with whom I could exchange my thoughts and was
very happy to get the proper suggestions/comments from the
pioneers of the field. This led to long-term implementation
possibilities of my research ideas mainly in RDBMS performance,
data mining and data warehousing here, at Oracle Corporation
where I am being able to contribute as the Principal Member
of our Performance team. Last but not the least, I want to
mention that I am very glad to have had the opportunity to
work in an industry oriented research environment of IMA.
Some of my IMA technical report abstracts are described in
the following paragraphs.
* Normal Distribution as a method for data replication in
a parallel data server:
Run-time load balancing is always a problem in scalable parallel
data servers because of initial data distribution. A data
warehouse is a scalable parallel server to operate on high
volumes of data for analytical processing. Relational model
implementations for analytical processing should incorporate
very fast operations like join, scan, sort, etc. Currently,
for shared-nothing MPP architecture, data is partioned at
load time in a shared-nothing way. The task distribution in
a join, scan and sort process is determined by the query optimizer
in a relational engine and there is no possibility of load
balancing at run-time because of the high network and I/O
cost. However, for a large number of nodes in a MPP architecture,
there may be a need for load sharing at run-time, unlike the
plan generated by the optimizer in relational engines. This
paper describes a theory for normal distribution of data from
a node to its immediate neighbouring nodes. This normal distribution
is implemented as a replication technique for small fractions
of data from a node to its adjacent nodes at load time. Since
a data warehouse is a read-only data service system, fractional
replications can be distributed without worrying about audit
or update. During run time, based on mutual agreements, task
load can be transferred from a node to its adjacent nodes,
for minimizing the overall time involved in relational operations.
This normal distribution of fractional replicated data leads
to a unique run-time solution for load balancing, not available
in current parallel data servers.
* A Graph Theoretic Approach for Parallel View Materialization
with Dynamic Load Balancing:
A View Cache is a stored collection of pointers pointing to
records of underlying relations needed to materialize a View.
This paper deals with the View Cache method of materialization
which has been proven to achieve both high performance and
efficient incremental updates. Using a bipartite graph representation
of a View Cache, the problem of optimal View materialization
has been posed as a problem of optimal traversal through the
edges of the graph. Next, this paper deals with an efficient
method of parallelizing this traversal using normal distribution
as a replication technique for small fractions of records
and ViewCache partitions.
* Internet and Relational Databases in a Multi-Tier Client/Server
This paper elaborates on the ideas of View Cache creation
and maintenance problems. Views are constructors for objects
sitting on top of relational databases. View Cache maintenance
and manipulations will answer the complex database question
for multi-tier client/server applications. A new idea of partial
exposition of data values in View Caches has been discussed.
Java bytecode along with view records can be transported to
other network nodes for materialization and computations.
This paradigm may add a completely new feature to object paradigm
and relational dbms integration.
Views and Data mining in a parallel data server
This paper describes how data mining can be performed on Views
in a parallel data server. A decision tree approach is considered
and tests are performed on a View Cache generated from relational
operations on the base level tables. Quinlan's ID3 algorithm
for a proper selection of attributes at a particular level
of the decision tree calculates the information gain for all
such attributes and considers the one with the maximal gain.
This requires multiple View materializations at a single level.
When we are considering a parallel data server, the number
of records in a View Cache may be skewed to a processor/s
and the materialization at any tree-level/s will not exploit
efficient parallelism. This paper gives a bipartite representation
of a View Cache and poses the problem of optimal view materialization.
* Data Mining on Views in Relational Databases using Bayesian
There are many different ways of representing knowledge, and
for each of these ways, there are different discovery algorithms.
This paper uses probabilistic graphical models as a unified
qualitative and quantitative framework for representing and
reasoning with probabilities and independencies and applies
such framework on Views in Relational Databases for data mining.
It considers a simple form of graphical model, the Bayesian
network and incorporates it on a View Cache hierarchy for
studying the dependency structure between several attributes
in a Relational Database, for knowledge discovery.
* Strategies for Optimal Performance of Relational Databases
High level query languages allow us to write queries that
take a great deal of time to execute, and their execution
time can be reduced greatly if the query language processor
rephrases the query before executing it. Such improvements
are called "optimizations" although the rephrased query need
not be optimal over all possible ways of implementing the
query and the term "improvement" would be more appropriate.
Other considerations are appropriate paralleization of query
execution, proper choice of indexing, mode of optimization
by optimizers and different replication scenarios. This paper
has touched upon different strategies of enhancing performance
in Relational databases.
from the University of New Hampshire (Mathematics Department)
I arrived at the IMA a few weeks after completing everything
I needed for my PhD. My first order of business was to prepare
two papers for publication from my dissertation. These were
co-written with Benito Chen and Myron Allen at the University
of Wyoming. These are described below:
Model of Flow, Transport and Biofilm Effects in Porous Media
describe how a porous media may be modeled as a set of interconnected
cylinders with varying diameters. One system of equations
is solved to determine flow rates through individual pores
in the medium. We show that the resulting system is symmetric,
positive definite. We also show how transport may be modeled
on this type of system.
Properties of Porous Media from a Network Model of Biofilm
We incorporate a number of species into the model described
in the first paper. The goal is to be able to model and predict
how flow properties of a porous medium change as a biofilm
grows in the pore spaces. Reaction and adsorption terms are
added to the advection-diffusion equation modeled in the first
paper. Numerical simulations are presented that highlight
effects of a few selected parameters.
completing these two papers, (both have recently been accepted
by "Transport in Porous Media.") Petter Bjørstad suggested
creating a parallel version of the code I had developed. I
created a 2-D and a 3-D version using Fortran and MPI for
message passing. We used an Additive Schwarz Domain Decomposition
algorithm to solve a pressure equation and an explicit scheme
for transport. I have a paper close to completion: "Parallel
Implementation of a Network Model for Flow through Porous
Media," that I hope to finish late 1997/early 1998. I presented
some results at seminars (interviews) at Los Alamos and the
University of New Mexico. The paper I am working on will compare
performance on the CRAY T3E and Origin 2000. The main focus
of the paper is on scaling the problem - keep the size of
the problem per processor the same and increase the number
of processors. I got a lot of help developing the code from
Petter and Barry Rackner.
I have one other paper that I began at the IMA tentatively
titled: "Peclet Number as a Function of Pore Radii Variance
Computed from a Network Model." It investigates how a network
model can be used to examine how varying pore radii influence
dispersion. Parallel solution will be included in this paper.
I attended a lot of tutorials, workshops and seminars. I knew
absolutely nothing about parallel computing before coming
to the IMA, and I consider myself a pretty competent parallel
programmer now. I was unaware of many of the issues surrounding
high performance computing before arriving at the IMA. Now
I feel confident enough to discuss PDE software and solutions,
domain decomposition, and scientific visualization software.
I also sat in on a class in the Computer Science department
on Iterative Methods by Yousef Saad. I hope to include ideas
developed while at the IMA in other papers, soon.
I guess I came to the IMA excited about landing an opportunity
to work around some pretty well-known mathematicians, and
a little intimidated. I know a lot of the other post-docs
had much stronger backgrounds than me. I think I learned more
last year than I did during any of my years at graduate school.
I was not prolific, but I put out a couple of papers last
year, and plan on putting out a few more this year. Two of
the papers I am currently working on were begun last year.
I spent much more time than I wanted to looking for a job
for this year. (It's going well, thank you.) I think it's
a good idea that future post-docs will be for two years.
Anyway, I enjoyed my time at the University of Minnesota.
I feel lucky to have been a part of the IMA.
of Seagate Technology provides a summary of his work at the
I was an IMA/Honeywell industrial postdoc from August 1995
to May 1997. It is really a great experience for me. Before
I came to the IMA, my research work (at the University of
Washington) concentrated on the perturbation method. While
at the IMA, my work is primarily on numerical PDEs. This transition
broadens my knowledge in applied mathematics and greatly enhances
my ability in numerical analysis and computation.
During the two years at IMA, I finalized two papers on Hamiltonian
system, in collaboration with Prof. J. Kevorkian at the University
of Washington. The two papers are published on Physics of
Plasmas and Physica D, respectively. I completed a project
on the modal analysis of homogeneous optical waveguides using
boundary integral formulation and Nystrom method, in collaboration
with Prof. Avner Friedman of the IMA and Dr. Allen Cox of
Honeywell. We developed an algorithm which can be used to
compute the eigenmodes of a multimode optical waveguide very
accurately. We also proposed, for the first time, the condition
under which the boundary integral formulation of homogeneous
optical waveguides has no spurious solutions. This work will
be published on the Journal of Optical Society of America
A in next January. I would like to thank Prof. Fernando Reitich
of North Carolina State University for introducing me the
Nystrom algorithm when he was an IMA visitor.
I also completed a project on the perturbation analysis of
multimode graded index fiber. I showed that the optical field
polarization has very little effect on pulse broadening in
the fiber, and the interactions between different modes are
very week and can be omitted. My work provides the mathematical
justification for the first order perturbation theory for
multimode optical fiber, which is widely used in the communication
industry. A paper based on this work is almost finished and
will be submitted to an optical journal.
I learned a lot on the numerical solution of nonlinear algebraic
equations from Prof. Eugene C. Gartland of Kent State University,
who is an IMA visitor in 1996. I also learned a great deal
on integral equations from Dr. Nie Qing and Dr. Jie Liang,
both of them were IMA postdocs in 1996-97. I learned many
different topics in applied mathematics from the numerous
workshops and seminars in 1995-97. In particular, the weekly
industrial mathematics seminar organized by Prof. Avner Friedman
will have the greatest impact on me. Now I am in the data
storage industry, doing mathematical modeling of magnetic
Wang, J.A. Cox and A. Friedman, "Modal Analysis of Homogeneous
Optical Waveguides by the Boundary Integral Formulation
and the Nystrom method," IMA preprint #1457, to appear in
J. Opt. Soc. Am. A (Jan. 1998).
Wang and J. Kevorkian, "Asymptotic electron trajectories
and an adiabatic invariant for a helical-wiggler free electron
lase with weak self-fields," Physics of Plasmas 3(1996)
Wang, D.L. Bosley and J. Kevorkian, "An asymptotic analysis
of the 1:3:4 Hamiltonian normal form", Physica D
99(1996) pp. 1-17.
and J. Allen Cox, "Effects of Polarization and Index Profile
Deformation on Optical Fiber Spectrum," in preparation.
of Wayne State University (Mathematics) reports the following
During my one year stay at the IMA for the Mathematics in
High Performance Computing program, I have attended important
workshops on Numerical solution of PDES, Numerical Software,
Adaptive Grid Generation, MPI, High Perform Fortran, etc,
which were very beneficial to me. I have learnt greatly about
the current research development of these areas and got to
know and talked with the leading figures of my areas.
On the research level, I have had important conversations
and information exchange with Mitchell Luskin, Bernardo Cockburn,
Petter Bjørstad, Sue Brenner, Chi-Wang Chu, Ridgway
Scott, Cai Xiao-Chuan, and many others.
I have also interacted with other postdoc members at the IMA
on a daily basis, which provide an active research environment.
In particular, I am collaborating with Qing Nie, a former
postdoc that I met during my stay at the IMA.
I have written three research papers which later became IMA
#1472, "Stabilized Schemes for Mixed Finite Element Methods
with Applications to Elasticity and Compressible Flow Problems;"
"Dynamic Finite Element Methods for Second Order Parabolic
"A Parallel Nonoverlapping Schwarz Domain Decomposition Method
for Elliptic Interface Problems."
In summary, my year at the IMA was very fruitful and I wish
I could spend more time there.
to top of page