University of Minnesota
University of Minnesota
http://www.umn.edu/
IMA Web

Research Accomplishments in Mathematics in High Performance Computing

1. ANNUAL PROGRAM ORGANIZERS

Petter E. Björstad of 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:

Summary

This 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.

Planning

The 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.

Organization

The 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 from abroad.

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 the IMA.

Practical Matters

This 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.

Workshops and Tutorials

I 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.

Post Doctoral Programme

The 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.

Science

The 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

Most 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.

Mitchell Luskin 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." He reports:

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 materials science.

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).

 

Top of page

 

2. WORKSHOP ORGANIZERS

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).

We hope that readers will find this collection as enjoyable and informative as we have.

Raymond Johnson 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:

  1. Overview talks by senior participants about their technical work and career experiences;

  2. Technical talks about the applications of mathematics associated with various real-world problems;

  3. Focused small-group discussions charged to produce action items for colleges and universities, government laboratories, funding agencies and professional organizations;

  4. 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 competitors.

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.

Breakout Group Recommendations

Each breakout group was asked to discuss the following topics:

  1. Undergraduate and graduate education in mathematical sciences
    • Transition from undergraduate to graduate work;
    • Curricular issues;
    • Uses of technology.

  2. Preparing for opportunities
    • Bridging the gap between academia and industry;
    • Breadth of training;
    • Role of interdisciplinary work;
    • Role of internships;
    • Entrepreneurs 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 one heading.)

A. Actions for everyone

  1. Get connected; have and use e-mail and internet access

  2. Make departmental presentations about this workshop; invite students from other departments

  3. Take advantage of computer center resources (C, C++, software packages, LATEX, UNIX, EXCEL)

  4. Encourage the Department to invite speakers who can give talks about applications of mathematics (and to make contacts with local industry)

  5. Attend seminars in other departments

  6. Contribute information to Internet sites for minorities (information about internships, co-ops, programs, etc.)

  7. Become aware of other minority/professional organizations

  8. Look for internships and summer appointments in industrial settings

  9. Keep in contact with mentors

  10. Set up a Web site on the Internet containing:
    1. Profiles of minority industrial mathematicians
    2. Names and research areas of minority graduate students who are working toward the Ph. D. degree; thesis topics when completed
    3. Profiles of minority businesses
    4. Listing of available internships
    5. Profile of tools needed for successful graduate experience (C, C++, Hypertext, GAMS, presentation skills, LATEX)
    6. Profile of conference abstracts, speakers, e-mail addresses, as in AARMS at http://www.wam.umd.edu/~rlj/aarms.html ; contribute to such sites
    7. Information on how to subscribe to minority e-mail lists
    8. Current sources of minority scholarships
    9. List of industrial and academic mentors
    10. 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
    11. Information about getting involved with "virtual" companies

  11. Use the Web to foster Applied Math team projects
    1. Identify hot areas in applied mathematics
    2. Recruit students
    3. Encourage students to form teams around these areas
    4. Support students planning and executing their chosen project
    5. Encourage student presentations on their projects at conferences

B. Actions for students

  1. Set a goal and remain focused on it

  2. Spend some time learning how to learn mathematics; take responsibility to prepare yourself

  3. Explore academic offerings of other departments to broaden research opportunities: take a computer course; perhaps minor in some area of engineering, science, business, etc.

  4. Develop facility with written/spoken language

  5. Get computational experience; learn a computer language and how to apply it to your problem

  6. Request a cross-departmental math modeling class with strong industry involvement

  7. Start an interdisciplinary journal club (students getting together to read articles from journals) or a graduate student seminar

  8. Get involved with a project involving applications or integrating math with other disciplines

  9. Make contact with other (minority) graduate students for possible collaboration on research-seek out a "like-minded" group

  10. Discuss with advisor "what lies ahead"

  11. Always keep your resume in mind
    1. 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
    2. Prepare for conferences by reading abstracts, deciding on talks you will attend and contacting authors of articles in which you are interested
    3. Do things inside and outside of school to make yourself more marketable
    4. When working on a project, always think about what part or extensions will be publishable

  12. Make an all-out effort before graduating and looking for a job
    1. Network at every opportunity-- attend seminars, attend conferences, e-mail authors of articles
    2. 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
    3. Ask professors and mentors to send recommendations; those based on personal contact are particularly important
    4. 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)
    5. Always follow up contacts
    6. Continually update your resume
    7. Stay aware of current events to facilitate conversations during job interviews
    8. 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

  1. Organize student-to-student forums conducted by graduate students for undergraduate student math majors to talk about the transition to graduate school

  2. 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 representatives

  3. Recognize and support students who plan to enter the job market with a B.S. or a M.S. degree

  4. Forward all job listings to all graduate students at all levels

  5. Offer a math modeling class where students can work on problems from industry-- expose students to working in teams and learning how to approach problems

  6. Make the modeling class interdisciplinary by cross-listing it with other departments

  7. Encourage students who want to take courses outside the Mathematics Department

  8. Invite speakers from industry to talk about real-world problems
    1. Contact graduates who work in industry
    2. Set up an Advisory Committee with invited representatives from local industry to provide another source of speakers

  9. Improve advising for graduate students; some groups even suggested development and use of a placement exam

  10. 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

  11. Be aware of students in other disciplines, such as EE, who take lots of mathematics, as sources of double majors and graduate students

  12. In industry, mathematics departments should explain their usefulness to the company; in academe, mathematical sciences departments should explain their usefulness to allied departments

D. Actions for professional societies

  1. Encourage student participation at meetings
    1. Organize events for students
    2. Support students' attendance at society meetings (as is done by the Society for Mathematical Biology)

Lawrence David Davis 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 to come.

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 it.

Michael Vose 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 its behavior.

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 concept.

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:

  1. Standard GA theory, from the perspective of logical rigor, leaves much to be desired.

  2. 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 analysis.

  3. That alternative points towards fixed points of an underlying dynamical system, among other things, as important objects in the theory.

  4. 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.

Darrell Whitley 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 this workshop.

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 experience.

Dianne P. O'Leary 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.

Tamar Schlick 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." She writes:

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...

Scott Baden 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." He writes:

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.

Christoph Borgers 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.

Some examples:

  1. Robert Levine made me much more aware of the importance of the beam selection (as opposed to beam weight optimization) problem in radiation therapy planning.

  2. 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 optimization problem.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

Frank Natterer 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." He reports:

The meeting brought together specialists from quite different fields. This resulted in many lively and often controversial discussions.

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 pre-selected beams.

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 transport equation.

Jeff Blaney 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:

PANEL DISCUSSION: NEW PROBLEMS THAT SHOULD BE ADDRESSED IN THE NEXT TEN YEARS

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 different response.

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.

A.J. Hopfinger and 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 as moderators:

PANEL DISCUSSION: IMPORTANT CURRENT PROBLEMS IN DRUG DESIGN THAT MAY BE COMPUTATIONALLY TRACTABLE

PANELISTS: DAVE DOHERTY, BILL DUNN, GRAHAM and RICHARDS DOUG ROHRER

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 procedure.

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 methods.

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.

Donald G. Truhlar from 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.

Fadil Santosa 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, and ADMIT-2.

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.

 

Top of page

 

3. SOFTWARE DEVELOPERS

At the April 21-15 IMA Tutorial on PDE SOFTWARE, eight software packages were presented by the developers or co-developers of each package:

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 PLTMG; and
Henrik Rentz-Reichert of the University of Stuttgart presented UG.

After the tutorial, the developers were asked to respond to the following questions:

  1. Which software package did you present?

  2. 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 scientific value).

  3. Did you try other software packages on other problems? Please describe the problems and your assessment of the software.

  4. Please make any other comments on your software and on the other software packages.

  5. 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.

GENERAL COMMENTS ON THE DIVERSITY OF SOFTWARE PACKAGES:

  • pltmg 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.

  • Most software packages are designed for:

      - Education
      - Research    or
      - Industrial application

    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.

  • There 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 system.

COMMENTS ON OTHER DEVELOPERS' SOFTWARE:

  • If 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, and GFEM.

  • I 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 problems.

    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.

  • The 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.

  • UG 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.

COMMENTS ON IMA WORKSHOP:

  • From 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.

  • Well 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 being scarce)

  • The 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!!!!
  • The 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.

  • The 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 support.

  • I 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.

 

Top of page

 

4. VISITORS/SPEAKERS

Duncan A. Buell 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 Sets" follows:

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.)

  • Observation 1:

    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.

  • Observation 2:

    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 problem.
    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 closure:

    1. Suppose 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."

    2. 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.

    Therefore:

    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) algorithm.

    It 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.

  • Example:

    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.

  • Bottom 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.

    Margaret Cheney 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!

    Papers:

    My first order of business was to finish revisions to a paper [1] 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 [2] 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 [3].

    People

    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 along.

    New Ideas

    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 good results.

    References

    [1] P. Bigeleisen and M. Cheney, "Models for an anesthesia breathing circuit," IMA preprint 1476. [2] M. Lassas and M. Cheney, "Uniqueness for a wave propagation inverse problem in a half space," in preparation. [3] M. Cheney, "Inverse boundary value problems," American Scientist, 85 (September-October 1997) 448-455.

    Rolf Clack 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 staff.

    I will probably be taking further advantage of your staff when I try to TeX (IMA-style) my report for the proceedings.

    Bernardo Cockburn 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 convection-diffusion equations.
    (2) With Pierre A. Gremaud, we were able to finish a paper devoted to a priori error estimates for nonlinear conservation laws.
    (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.

    Laurent Desbat 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 follows:

    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 simply great!

    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 (sets
$\{Wk,k\in\bZ^n$) 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 [3] the sampling condition of the X-ray transform $\P f(\zeta,x) =\int_{-\infty}^{\infty}f(x+t\zeta)dt$ with $\zeta$ in the unit circle and $x\in\zeta^\perp$, more precisely of $g(\phi,s,t)=\P f(\zeta, s
\theta + t e_3)$, $\phi\in[0,2\pi]$, $\zeta=(-\sin \phi,\cos
\phi,0)^t$, $\theta=(\cos\phi,\sin \phi,0)^t$, $s\in [-1,1],t\in $[-1,1]$, $e_3=(0,0,1)^t$. 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 industrial tomography[1,2].

    Our recent work thus concerns 3D [3]. 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[4]. I could also work with David Walnut on multidimensional sampling on unions of lattices, which could have very nice practical applications in tomography.

    REFERENCES

    [1] L. Desbat. Efficient sampling on coarse grids in tomography. Inverse problems, 9:251-269, 1993.

    [2] L. Desbat. 3D efficient parallel sampling perturbation in tomography. In International Meeting on Fully 3D Image Reconstruction in Radiology and Nuclear Medicine, 1997.accepted.

    [3] L. Desbat. Echantillonnage parallhle efficace en tomographie 3D. C.R. Acad. Sci. Paris, Séerie I, t. 324, pages 1193-1199, 1997.

    [4] L. Desbat and C. Mennessier. Efficient sampling in Doppler imaging. Proceedings of SampTA, 1997. accepted.

    Keneth A. Dill 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 been great!

    Xiaobing Feng 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.

    Ronald H.W. Hoppe 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 Numerical Mathematics."

    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" in 1998.

    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 co-operation.

    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.

    Guido Kanschat from Universität Heidelberg (Institut für Angewandte Mathematik) was a visitor from May 29 - June 29, 1997. has the following report:

    PARALLEL 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 (kappa, sigma 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.

    Ralph E. Kleinman 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.

    Martin Kruzík of the Czech Academy of Sciences (Decision-making Theory) reports:

    My 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 [1] and have been working on several projects.

    First, I finished the final version of my paper [2] 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.

    The second paper written during my stay in the IMA is [3]. This paper is devoted to investigation of geometric properties of sets of (generalized) Young functionals. Roughly speaking, taking a bounded sequence $\{u_k\}_{k\in\N}\subset L^p(\O;\R^m)$, where $\O\subset\R^n$ and bounded we define the Young functional $\eta\in H^*$ as (after possible extraction of a subsequence) $\lim_{k\to\infty}\int_{\O}h(x,u_k(x))\,{\rm d}x=\left\langle\eta,h\right\rangle$, where $h\in H$ for $H$ 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 sigma-compact; cf. [8]. 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 [4] 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 [5]. Especially, we are about to establish results concerning convergence and error estimates. Further, we will apply our methods to examples from the optimal control theory.

    In the second paper [6] 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 [7] (together with M. Luskin) contains three-dimensional problems solved in [2] 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.

    REFERENCES

    [1] M. Kruzík: Oscillations, Concentrations and Microstructure Modeling., Ph.D. thesis, Charles University, Prague, 1996.

    [2] M. Kruzík: Numerical approach to double well problems., accepted.

    [3] M. Kruzík, T. Roubícek: Geometric properties of generalized Young functionals., submitted.

    [4] M. Kruzík: DiPerna-Majda measures and uniform integrability., submitted.

    [5] M. Kruzík, T. Roubícek, M. Vítková: Optimal control problems admitting concentrations and oscillations effects and their numerical treatment., in preparation.

    [6] M. Kruzík: Numerical solution to relaxed problems in micromagnetics., in preparation.

    [7] M. Kruzík, M. Luskin: Numerical solutions to three-dimensional double well problems., in preparation.

    [8] T. Roubícek: Relaxation in Optimization Theory and Variational Calculus., W. de Gruyter, Berlin, 1997.

    Jon C. Luke of Indiana University/Purdue University IUPUI(Mathematical Sciences) writes:

    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.

    Andreas Prohl 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 [3] 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 convex problems.
    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 results:

    1. Proposal of a new finite element method suitable for resolving simply laminated microstructure on general grid topologies,

    2. Presentation 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,

    3. Computational 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 [1] and [2]. 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, [6], [7]. 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 conditions.

    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, [4].

    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.

    REFERENCES

    [1] Matthias Gobbert and Andreas Prohl, On a new finite element method for solving a multi-well problem, in preparation

    [2] Matthias Gobbert and Andreas Prohl, A comparison of classical and new methods for approximating laminated microstructure, in preparation

    [3] Mitchell Luskin, On the computation of crystalline microstructure, Acta Numerica (1996).

    [4] Andreas Prohl, Projection and Quasi-Compressibility Methods for Solving the Incompressible Navier-Stokes Equations, Teubner (1997).

    [5] Andreas Prohl, An adaptive method for computing laminated microstructure, in preparation

    [6] Andreas Prohl, Proposal and analysis of a first-order projection-based time-splitting scheme for solving a model for chemically reacting flows, in preparation

    [7] Andreas Prohl, Proposal and analysis of a second-order projection-based time-splitting scheme for solving a model for chemically reacting flows, in preparation

    Rolf Rannacher 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 interest are:

    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.

    Activities:

      - 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 at IMA)

    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.

    Activities:

      - 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 methods.

    Activities:

      - 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

    (Special 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."

    Activities: - 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 at IMA)

    Thanks again for this pleasant time at the IMA.

    Rosemary Renaut 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 will materialize.

    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 the IMA.

    Research Projects

    Numerical 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.

    Multisplitting Methods for Solution of Least Squares Problems

    The 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 Schwarz methods.

    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.

    Publications and Reports

    • R.A. Renaut , "Evaluation of Chebychev Pseudospectral Methods for Third-Order Differential Equations." Numerical Algorithms, submitted .

    • A. Frommer and R. A. Renaut, "Parallel Subspace Decomposition Methods for Quadratic Functionals," in preparation.

    Chi-Wang Shu 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 arrangements.

    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:

    1. We 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.

    2. We 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.

    The following two IMA preprints summarize the results:

    1. B. 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 Analysis.

    2. B. 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 Physics.

    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 ongoing.

    Paul Siegel from University of California, San Diego (Electrical and Computer Engineering) was a visitor from November 10 - 15, 1997. He expresses:

    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.

    Vladimir Sverak from 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:

    1. 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)

    2. "supervising" (or at least providing some guidance to) Martin Kruzik, a Sloan Fellow, who stayed at the IMA for most of the year

    3. 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 questions.

    Plechac and I will write a joint paper explaining our approach and our conclusions.

    Paul Thompson 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 are introduced.

    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.

     

    Top of page

     

    5. POSTDOCS

    Matthias K. Gobbert 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 Series.

    1. Matthias K. Gobbert and Andreas Prohl, On Finite Element Methods for Solving a Multi-Well Problem.

    2. Matthias K. Gobbert and Andreas Prohl, A Comparison of Classical and New Finite Elements for the Computation of Crystalline Microstructure.

    Michael A. Kouritzin of the University of Alberta, Department of Mathematical Sciences

    IMA 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.

    REFERENCES

    [1] D. Dawson and M. A. Kouritzin. Invariance principles for parabolic equations with random coefficients. J. Functional Analysis, 149:377-414, 1997. IMA Preprint #1433.

    [2] M.A. Kouritzin. Averaging for fundamental solutions of parabolic equations. J. Differential Equations, 136:35-75, 1997. IMA Preprint #1379.

    [3] M.A. Kouritzin. Approximations for higher order parabolic equations. Submitted. IMA Preprint #1444.

    [4] 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.

    [5] M.A. Kouritzin, "On exact filters for continuous signals with discrete observations", to appear in the IEEE Transactions on Automatic Control. IMA Preprint #1409.

    [6] M.A. Kouritzin, "Arbitrary order parabolic stochastic partial differential equations with general Hilbert-space-valued noise", The IMS Bulletin 26 (1997) pp. 322-323.

    [7] 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.

    Sergey Lototsky 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 equations.

    1. 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 recognition, etc.)

    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 algorithm.

    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, February 1997.

    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 Martin Corporation.

    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 Genetic Algorithms.

    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 were prepared:

  • 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.

    3. 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 genetics.

    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 Analysis (submitted).

    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 domains.

    II. 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.

    Brian T. Nguyen 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:

    1. 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 equation

    We 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.

    2. A Posteriori Error Analysis for Hyperbolic Equations

    This 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[1] has shown for the equation

    that if u(x,t) is an approximate solution with residual R(u), then the error norm ||v-u|| satisfies

    Our 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.

    3. Other activities

    • Chaired fall term postdoc seminars

    • Published article entitled "On Comparisons of Time-Domain Scattering Schemes"[4], 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.

    • Submitted paper entitled "Solitary Waves in the Critical Surface Tension Model"[3]

    • Presented a poster on the upwind-leapfrog method for electromagnetic and acoustic scattering predictions at the University of Michigan, Godunov Seminar.

    REFERENCES

    [1]Bernardo Cockburn. Personal Communication, 1996.

    [2]

    [3]Yi 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).

    [4] Brian T. Nguyen. On comparisons of time-domain scattering schemes. IEEE Antennas and Propagation Magazine, 39(1):99-102, February 1997.

    Sanhita Sarkar 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.

    Research Reports:

    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 Model:

    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 Networks

    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.

    Brian J. Suchomel from the University of New Hampshire (Mathematics Department) writes:

    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:

    Network Model of Flow, Transport and Biofilm Effects in Porous Media

    We 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.

    Macroscale Properties of Porous Media from a Network Model of Biofilm Processes

    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.

    After 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.

    Lei Wang of Seagate Technology provides a summary of his work at the IMA:

    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 recording head.

    Research Papers:

    1. L. 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).

    2. L. 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) pp. 1162-1175.

    3. L. 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.

    4. L.Wang and J. Allen Cox, "Effects of Polarization and Index Profile Deformation on Optical Fiber Spectrum," in preparation.

    Daoqi Yang of Wayne State University (Mathematics) reports the following activities:

    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 preprints:

    #1472, "Stabilized Schemes for Mixed Finite Element Methods with Applications to Elasticity and Compressible Flow Problems;"

    #1489, "Dynamic Finite Element Methods for Second Order Parabolic Equations;" and

    #1508, "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.

     

    Back to top of page