This document summarizes activities of the ITL Mathematical and Computational Sciences Division for FY 1999, including technical highlights, project descriptions, lists of publications, and examples of industrial interactions.

1. Ron Boisvert, Roldan Pozo, and Bruce Miller discuss the SciMark benchmark developed for the Java Grande Forum.
2. Isabel Beichl teaches a course on no-numeric algorithms for scientific computing.
3. Chris Witzgall (far left) and Javier Bernal (far right) discuss use of terrain modeling in automated monitoring construction site activity with colleagues from the NIST Building and Fire Research Laboratory.

Micrograph of a thermal barrier coating (top left) and its realization in OOF.

The mission of the Mathematical and Computational Sciences Division (MCSD) is as follows.

Within the scope of our charter, we have set the following general goals.

• Insure that sound mathematical methods are applied to NIST problems.
• Improve the environment for computational science and engineering within NIST as well as within the external community.

With these goals in mind, we have developed a technical program in three general areas.

1. Mathematical modeling in the physical sciences, engineering, and information technology.
2. Development of algorithms and tools for high-performance mathematical computation.
3. Development and dissemination of mathematical reference information.

The first area is done primarily via collaborations with other technical units of NIST. Projects in the second area are typically motivated by internal NIST needs, but have products, such as software, which is widely distributed. The third area reflects work done primarily for the computational science community at large, although NIST staff benefits.

We have developed a variety of strategies to increase our effectiveness in dealing with such a wide customer base. We take advantage of leverage provided via close collaborations with other NIST units, other government agencies, and industrial organizations. We develop tools with the highest potential impact, and make online resources easily available. We provide educational and training opportunities for NIST staff. Finally, we select areas for direct external participation that are fundamental and broadly based, especially those where measurement and standards can play an essential role in the development of new products.

Division staff maintain expertise in a wide variety of mathematical domains, including linear algebra, special functions, partial differential equations, computational geometry, Monte Carlo methods, optimization, inverse problems, and nonlinear dynamics. Application areas in which we have been actively involved in this year include materials science, fluid mechanics, electromagnetics, manufacturing engineering, construction engineering, wireless communications, optics, bioinformatics, image analysis and computer graphics.

Output of Division work includes publications in refereed journals and conference proceedings, technical reports, lectures, short courses, software packages, and Web services. In addition, MCSD staff members participate in a variety of professional activities, such as refereeing manuscripts and proposals, service on editorial boards, conference committees, and offices in professional societies. Staff members are also active in educational and outreach programs for mathematics students at all levels.

A list of recent activities in each of the division focus areas follow. Note that individual projects may have complementary activities in each of these areas. For example, the micromagnetic modeling work has led to the OOMMF software package, as well as to a collection of standard problems used as benchmarks by the micromagnetics community. Further details on many of these efforts can be found in Part II of this report.

• Modeling of
• acoustic emissions for nondestructive testing (with BFRL)
• alloy solidification (with MSEL)
• construction sites (with BFRL)
• electron microscope scans (with EEEL)
• genome sequences (with CSTL)
• high-speed metal cutting (with MEL)
• material microstructures (with MSEL)
• micromagnetic systems (with MSEL, EEEL)
• optical computing systems (with ITL)
• optical reflectance of surfaces (with BFRL, PL, MEL)
• signal sets for wireless communications (with ITL, EEEL)

• Delauney triangulations for large-scale terrain modeling
• f90gl: standard Fortran 90 bindings and reference implementation for OpenGL 3D graphics
• Image deblurring
• Importance sampling techniques for computing matrix permanents and its application to dimer covering and the partition function
• JAMA: an API and reference implementation for numerical linear algebra in Java
• OOF: object-oriented finite element analysis system for real material microstructures
• OOMMF: object-oriented micromagnetic computing framework
• PHAML: Parallel Hierarchical Adaptive Multi-Level solver for partial differential equations
• Sparse BLAS: standard APIs for basic sparse linear algebra operations
• Time-domain algorithms for acoustic and electromagnetic scattering
• TNT: Template Numerical Toolkit for C++
• Truncated singular-value decomposition for ill-posed problems

• Digital Library of Mathematical Functions: modern online successor to the classic NBS Handbook of Mathematical Functions (with PL)
• Guide to Available Mathematical Software (GAMS): a cross-index and virtual repository of mathematical and statistical software components for use in computational science and engineering research
• High-precision reference algorithms and software for the complex Airy, Scorer, and Macdonald functions
• Matrix Market: a visual database of matrix data for use in the comparative study of algorithms and software for numerical linear algebra
• SciMark: an online benchmark for numerical computing in Java
• Standard problems for assessing the performance of micromagnetic modeling software

To complement these activities, we engage in short-term consulting with NIST scientists and engineers, conduct a lecture series, and sponsor shortcourses and workshops in relevant areas. Information on the latter can be found in Part III of this report.

In this section, we highlight a few of the significant accomplishments of MCSD this past year. Further details on the technical accomplishments of the division can be found in Parts II and III.

Digital Library of Mathematical Functions Receives NSF Support. In September 1999, MCSD received substantial funding from the National Science Foundation to support the development of the NIST Digital Library of Mathematical Functions (DLMF). The NIST proposal entitled Mathematical Foundations for a Networked Scientific Knowledge Base was awarded $1.3M over three years by the NSF Knowledge and Distributed Intelligence (KDI) program with support from the Division of Mathematical Sciences and the Division of Information and Intelligent Systems. The NIST award was one of 31 given by the KDI program in FY 1999, and the only one awarded to a non-academic institution.

The DLMF will provide NIST-certified reference data and associated information for the higher functions of applied mathematics. Such functions possess a wealth of highly technical and critically important properties that are used by engineers, scientists, statisticians, and others to aid in the construction and analysis of computational models in a variety of applications. The DLMF will deliver this data over the World Wide Web within a rich structure of semantic-based representation, metadata, interactive features, and internal/external links. It will support diverse user requirements such as simple lookup, complex search and retrieval, formula validation and discovery, automatic rule generation, interactive visualization, custom data on demand, and pointers to software and evaluated numerical methodology.

The DLMF was conceived as the successor for the NBS Handbook of Mathematical Functions (AMS 55), edited by M. Abramowitz and I. Stegun and published by NBS in 1964. AMS 55 is possibly the most widely distributed and cited NBS/NIST technical publication of all time. (The U.S. Govt. Printing Office has sold over 150,000 copies, and commercial publishers are estimated to have sold several times that number). The DLMF is expected to contain more than twice as much technical information as AMS 55, reflecting the continuing advances of the intervening 40 years.

The DLMF is being developed by a team of researchers in ITL and PL led by Daniel Lozier, Frank Olver, Charles Clark and Ron Boisvert. Additional support is being provided by MEL's Systems Integration for Manufacturing Applications (SIMA) program, TS's Standard Reference Data Program, and the ATP Adaptive Learning Systems program. NSF funding will be used to contract for the services of experts on mathematical functions to develop and validate the technical material that will make up the DLMF. The project is a substantial undertaking, with some 60 participants expected from outside NIST.

OOF Named Technology of the Year. In December 1999 Industry Week magazine named NIST as one of its 1999 Technology of the Year award winners for the development of OOF. OOF is an object-oriented finite-element system for the modeling of real material microstructures. It was created by Steve Langer of MCSD in collaboration with Andy Roosen and Ed Fuller of the NIST Materials Science and Engineering Laboratory (MSEL), and Craig Carter of MIT (formerly of MSEL). OOF shared the spotlight with technologies such as a roentgen high-resolution flat-panel display from IBM, and Toyotas Pirius hybrid gas/electric vehicle.

The OOF user begins with a realistic microstructural geometry by loading a two dimensional image of a real or simulated material into the program. The behavior of a material on the macroscopic scale depends to a large extent on its microstructure, the complex ensemble of polycrystalline grains, second phases, cracks, pores, and other features existing on length scales large compared to atomic sizes. OOF allows materials scientists to determine the influence of microstructure on a material's macroscopic properties through an easy-to-use graphical interface. Features in the image (e.g., grains, pores, and grain boundaries) are identified and assigned local material properties (e.g. crystalline symmetry and orientation, elastic constants, or thermal expansion coefficients). By applying stresses, strains, or temperature changes the user can measure the effective macroscopic material behavior, or can examine internal stress, strain, and energy density distributions. OOF currently handles only thermoelasticity, but extensions to other material properties are planned.

Beginning in FY2000 the OOF team will be cooperating with scientists at General Electric in a DOE-sponsored project to investigate the use of OOF as a quality control tool on the shop floor. It will be extended to simulate the performance of thermal barrier coatings for turbine blades.

Java Numerics Project Leads to Changes in Java. Java, a network-aware programming language and environment developed by Sun Microsystems, has already made a huge impact on the computing industry. Recently there has been increased interest in the application of Java to high performance scientific computing. Recommendations of a technical working group chaired by MCSD were instrumental this year in the adoption of a fundamental change in the way floating-point numbers are processed in Java. This change will lead to significant speedups to Java code running on Intel microprocessors like the Pentium. The recommendations were made by the Numerics Working Group of the Java Grande Forum (JGF), a consortium of industry, government, academia participants interested in the use of Java for high-performance computing applications. Ron Boisvert and Roldan Pozo co-chair the working group. Participants include IBM, Least Squares Software, Numerical Algorithms Group, Visual Numerics, The MathWorks, Syracuse University, the University of Tennessee at Knoxville, and the University of California at Berkeley.

All Java programs run in a portable environment called the Java Virtual Machine (JVM). The behavior of the JVM is carefully specified to insure that Java codes produce the same results on all computing platforms. Unfortunately, emulating JVM floating-point operations on the Pentium leads to a four- to ten-fold performance penalty. The Working Group studied an earlier Sun proposal, producing a counter-proposal which was much simpler, more predictable, and which would eliminate the performance penalty on the Pentium. Sun decided to implement the key provision of the Numerics Working Group proposal in Java 1.2, which was released in the spring of 1999.

Tim Lindholm, Distinguished Engineer at Sun, one of the members of the original Java project, the author of The Java Virtual Machine Specification, and currently one of the architects of the Java 2 platform said:

The working group also advised Sun on the specification of elementary functions in Java, which lead to improvements in Java 1.3 which was released in the fall of 1999.

Advances in Blind Deconvolution. Alfred Carasso has made some remarkable early advances this year in so-called blind deconvolution. In this problem, one seeks to deblur an image without knowing the cause of the blur. This is a very difficult mathematical problem. Existing approaches have been iterative in nature, but are both computationally intensive and unreliable. Rather than attempting to solve the problem in its full generality, Carasso identifies a wide class of important blurs that includes and generalizes Gaussian and Lorentzian distributions (class G). Likewise, a large class of sharp images is characterized in terms of its behavior in the Fourier domain (class W). Based on empirical observations which have not previously been exploited, Carasso has shown how 1-D Fourier analysis of blurred image data can be used to detect class G point spread functions acting on class W images. A separate image deblurring technique uses this detected point spread function to deblur the image. Each of these two steps uses direct non-iterative methods, and requires interactive adjustment of parameters. With this approach, blind deblurring of 512x 512 images can be accomplished in minutes on current desktop workstations. The technique has been successfully applied to images from the NIST Physics Lab, as well as to a wide variety of test images. This work has just been written up, but it is already attracting wide interest.

Awards. Several staff members received significant awards this year in addition to the Industry Week Technology of the Year Award received by Stephen Langer and OOF.

Anthony Kearsley was one of two NIST staff members selected to receive the Presidential Early Career Award for Scientists and Engineers from the National Science and Technology Council. The award is given to those who, while early in their careers, show exceptional potential for leadership at the frontiers of scientific knowledge during the twenty-first century. He was cited for his work in the application of optimization methods in a wide variety of areas. (Roldan Pozo of MCSD won this award in 1996.) Later in the year, Kearsley received a joint invitation from the U.S. National Academy of Science and the Chinese Academy of Science to participate in the second annual Frontiers in Science Symposium, which was held in Beijing on August 20-22. This invitational symposium brought together outstanding American and Chinese scientists from many disciplines to discuss important technical challenges facing their fields.

In January 2000, the Association for Computing Machinery (ACM) named Ronald Boisvert as the winner of the 1999 Outstanding Contribution to ACM Award. Boisvert was cited for his "leadership and innovation as Editor-in-Chief of the ACM Transactions on Mathematical Software and his exceptional contributions to the ACM Digital Library project". ACM has honored 29 people for service to the society since the awards inception in 1976. Boisvert will receive the award at ACMs annual awards ceremony to be held in San Francisco in May 2000.

Technology Transfer. MCSD staff members continue to be active in publishing the results of their research. This year 32 publications appeared which were authored by Division staff, 21 of which appeared in refereed journals. Fourteen additional papers have been accepted for publication in refereed journals. Another 16 manuscripts have been submitted for publication and 27 are being developed.

MCSD staff members were also invited to give 40 lectures in a variety of venues and contributed another 19 talks at conferences and workshops. Two shortcourses where provided by MCSD for NIST staff this year. Isabel Beichl presented Non-numerical Methods for Scientific Computing and William Mitchell presented another on Fortran 90 for Scientists and Engineers. Both were very well attended. The Division lecture series remained active, with 26 talks presented (nine by MCSD staff members); all were open to NIST staff. In addition, MCSD staff members were involved in the organization of nine external conferences, workshops, and minisymposia.

Software continues to be a by-product of Division work, and the reuse of such software within NIST and externally provides a means to make staff expertise widely available. This year saw the initial release of the SciMark benchmark, a collection of Java applets and related software for measuring the performance of Java Virtual Machines for numeric-intensive computation. Faculty appointee G. W. Stewart issued the first release of Jampack, a Java package for numerical linear algebra. In contrast to the user-level Jama package released by the MathWorks and MCSD last year, Jampack is based upon a design that provides extensive features to linear algebra experts; it also supports complex matrices. Several existing MCSD software packages saw new releases this year, including OOMMF (micromagnetic modeling), f90gl (OpenGL graphics interface for Fortran 90), and TNT (Template Numerical Toolkit for numerical linear algebra in C++).

Web resources developed by MCSD continue to be among the most popular at NIST. The MCSD Web server at math.nist.gov has serviced more than 20 million Web hits since its inception in 1994 (7 million of which have occurred in the past year!) Altavista has identified more than 5,000 external links to the Division server. The NIST Guide to Available Mathematical Software (GAMS), a cross-index and virtual repository of mathematical software, is used more than 10,000 times each month. During a recent 36-month period, 34 prominent research-oriented companies in the .com domain registered more than 100 visits apiece to GAMS. The Matrix Market, a visual repository of matrix data used in the comparative study of algorithms and software for numerical linear algebra, sees more than 100 users each day. It has distributed more than 16 Gbytes of matrix data, including more than 64,000 matrices, since its inception in 1996.

Professional Activities. Division staff members continue to make significant contributions to their disciplines through a variety of professional activities. This year Daniel Lozier was elected chair of the SIAM Special Interest Group on Orthogonal Polynomials and Special Functions. Ronald Boisvert continues as a member of the ACM Publications Board.

Division staff members continue to serve on journal editorial boards. Ronald Boisvert serves as Editor-in-Chief of the ACM Transactions on Mathematical Software. Daniel Lozier is an Associate Editor of Mathematics of Computation and the NIST Journal of Research. Geoffrey McFadden is an Associate Editor of Journal of Computational Physics, SIAM Journal of Applied Mathematics, as well as the new journal Interfaces and Free Boundaries

Division staff members work with a variety of external working groups. Ronald Boisvert and Roldan Pozo chair the Numerics Working Group of the Java Grande Forum. Roldan Pozo chairs the Sparse Subcommittee of the BLAS Technical Forum. Michael Donahue and Donald Porter are members of the Steering Committee of muMag, the Micromagnetic Modeling Activity Group. Ronald Boisvert is a member of the International Federation of Information Processing (IFIP) Working Group 2.5 (Numerical Software) of Technical Committee 2 (Programming Languages).

Four staff members and one postdoc left MCSDs ranks during this year. James Blue, leader of the Mathematical Modeling Group, retired in September 1999 after 20 years of service to NBS/NIST. John Gary, an MCSD staff member in Boulder, retired in December 1998 after more than 15 years of service to NBS/NIST. Both Blue and Gary have retained affiliation with MCSD as guest researchers. Janet Rogers, a 30-year NBS/NIST veteran in Boulder, retired in June 1999. She is pursuing a new career in economic modeling for the governor of Colorado. Karin Remington left in January 1999 to pursue a career in bioinformatics at Celera Genomics in Rockville, MD. Finally, Bruce Fabijonas completed his two-year tenure as a NRC postdoctoral appointee, taking a tenure track position in the Mathematics Department at Southern Methodist University.

David Sterling, who recently received a Ph.D. in mathematics from the University of Colorado, joined the NIST staff in Boulder in the fall of 1998 as a NRC postdoctoral appointee. In the fall we also made an offer to a recent Ph.D. to join the MCSD staff in Boulder. We expect this person to come on board in March 2000.

Finally, in late 1999 Joyce Conlon was transferred to MCSD from the ITL High Performance Systems and Services Division. She will be providing systems and programming support to a number of division projects.

Two MCSD staff members are currently on developmental assignments. Anthony Kearsley is spending half time at Carnegie-Mellon University during FY1999 and FY2000. He is working with researchers in the Computer Science Department there on applications of optimization methods to problems in networking and computer security. Bradley Alpert began a year visit at the Courant Institute of NYU where he is working with Leslie Greengard and colleagues on fast semi-analytic methods with applications in electromagnetic modeling.

Student Employment Program. MCSD provided support for seven student staff members on summer appointments during FY 1999. Such appointments provide valuable experiences for students interested in careers in mathematics and the sciences. In the process, the students can make very valuable contributions to MCSD programs. This years students were as follows.

Employee Survey. In the spring of 1999, NIST contracted with an independent firm to survey all employees, asking detailed questions regarding the NIST work environment. The results were aggregated at the NIST, Laboratory, and Division levels and presented to all NIST staff. For MCSD, the results showed general satisfaction with the Division-level work environment. Staff members feel that their colleagues are skilled, cooperative, and motivated. First line managers are supportive and responsive. Staff members understand what is expected of them, and have the tools and authority needed to carry out their jobs. The survey also uncovered some serious concerns with the research environment within the NIST Labs in general and ITL in particular. Several division meetings were held to discuss the concerns of staff. These culminated in the development of a Division action plan outlining steps that should be taken at the Division, Lab, and NIST level to address staff concerns. Several of these have begun to be implemented at the Division level. Division recommendations have been folded into a Laboratory level action plan.

Strategic Planning. This year MCSD initiated a formal strategic planning process. All staff members participated in several meetings in which several views of future technical issues affecting Division work were proposed and discussed. A consensus was obtained on major areas in which MCSD should play a role, and specific recommendations for future actions were laid out. The major trends identified as part of the strategic vision of the division are summarized below.

• Measurement and Calibration for the Virtual Sciences

• Evolving Architecture of Tools, Libraries, and Information Systems for Science and Engineering

• Emerging Needs for Applied Mathematics

These issues, as well as proposed MCSD responses, are detailed in the MCSD Strategic Plan, available upon request. The MCSD plan provided input to the ITL Strategic Plan, which has just been finalized. MCSDs plans are consistent with those of the Laboratory and of NIST as a whole.

Olga Taussky Todd Conference. Several MCSD staff members participated in a symposium honoring Olga Taussky Todd, a mathematical pioneer and a former staff member of NBS, held July 16-18, 1999 at the Mathematical Sciences Research Institute in Berkeley, California. The symposium, entitled "The Olga Taussky Todd Celebration of Careers in Mathematics for Women" was organized and sponsored by the American Women in Mathematics (AWM). Besides honoring Taussky Todd (1906-1995), one of the century's most important American mathematicians, the symposium showcased contemporary women mathematicians whose careers mirror aspects of Taussky Todd's work. A third objective was to foster the careers of upcoming female mathematicians. During the 1950's, Taussky-Todd and her husband John Todd worked for the Institute for Numerical Analysis (INA), part of the Applied Mathematics Laboratory of the National Bureau of Standards housed on the campus of University of California at Los Angeles (UCLA). Isabel Beichl, an MCSD mathematician, and Dianne O'Leary, Professor of Computer Science at the University of Maryland and MCSD faculty appointee, were members of the organizing committee. Beichl also gave a presentation about Taussky Todd's years at NBS. MCSD mathematician Fern Hunt was a plenary speaker. In a talk entitled, "A Mathematician at NIST Today" she spoke about current interdisclipinary research on the light scattering properties of coated surfaces. All three staff members participated in the mentoring activities that were a uniquely engaging and lively part of the conference.

Dr. Hunt is collaborating with Gary Meyer of the University of Oregon and Gregory Ward Larson of Silicon Graphics Inc. This work is part of a competence project on the appearance of painted and coated surfaces involving four laboratories, ITL, BFRL, MEL, and PL. In addition to the rendering work, Dr. Hunt has also been modeling the microstructure of metallic coatings using point processes.

Highlights for FY 1999 included the following.

• Gregory Ward Larson SGI and author of the rendering program RADIANCE renders automobile from optical measurements of car panels coated with gray metallic paint. The measurements were taken by Maria Nadal and Yvonne Barnes of PL.
• Gary Meyer and student Harold Westlund developed an interface between RADIANCE and a database of optical scattering (BRDF) measurements. They used a measurement format based on the NEFDS database, a set of government measurements previously acquired by Hunt. Images rendered from the NEFDS can be found on the project Web page.
• Meyer and Westlund used the interface enhanced rendering program to render the appearance of coated black glass samples. These samples were developed, measured, and analyzed by the competency group in order to perform a gloss loss study. Meyer and Westlund used surface topographical measurements (performed by Ted Vorburger of MEL) of the samples. The measurements were used to compute a model BRDF function, which was then used as input for the program. The model was developed by Egon Marx of MEL.
• Hunt engages Michael Metzler of ISCIENCES, the author of the engineering code used in the NEFDS to develop a measurement protocol to be used to supply parameters for the BRDF model used in the rendering program. The protocol has been developed and PL has purchased the equipment necessary to carry it out.
• Third year review of the project was performed by the Director and Deputy Director of NIST
• Hunt reports on the rendering work to a group of industrial researchers from DuPont, Ford, and other companies concerned with paint and coatings at a meeting of the Service Life Prediction Consortium
• The competency group plans a workshop on metrology and measurement of color and appearance, to be held at NIST in March. F. Hunt is organizing a session on rendering.    

Blind deconvolution seeks to deblur an image without knowing the cause of the blur. This is a difficult mathematical question that is not fully understood. For example, the 1D problem turns out to be harder than the 2D problem! So far, most approaches to blind deconvolution have been iterative in nature, but the iterative approach is generally ill behaved, often developing stagnation points or diverging altogether. When the iterative process is stable, a large number of iterations may be necessary to resolve fine detail.

The present approach does not attempt to solve the blind deconvolution in full generality. Rather, attention is focused on a wide class of blurs that includes and generalizes Gaussian and Lorentzian distributions, and has significant applications. This is the class G. Likewise, a large class of sharp images is exhibited and characterized in terms of its behavior in the Fourier domain.  This is the class W. It is shown how 1-D Fourier analysis of blurred image data can be used to detect class G point spread functions acting on class W images. This approach is based on empirical observations about the class W that have not previously been exploited in the literature. A separate image deblurring technique uses this detected point spread function to deblur the image. Each of these two steps uses direct non-iterative methods, and requires interactive adjustment of parameters. As a result, blind deblurring of 512x 512 images can be accomplished in minutes of CPU time on current desktop workstations. This is considerably faster than what is currently feasible by iterative methods.

There is a great deal of interest in blind deconvolution at several U.S. Government Laboratories, including the Air Force Phillips Laboratory where tracking and monitoring of orbiting space objects is a major activity. Blind deconvolution is also an active field of research at several universities, including Minnesota, Stanford, and UCLA. At NIST, this approach has been successfully applied to improve images obtained from several types of electronic microprobes in use in the NIST Surface and Microanalysis Sciences Division.

Analysis of the blind problem within the class G has produced a number of interesting and unexpected results. These results can stimulate further research by other investigators. This work is totally original and has opened new avenues in this difficult subject. Current research aims at developing direct methods that can be applied to important types of blurs not included in G.

Timothy Burns
Matt Davies (NIST MEL)
Chris Evans (NIST MEL)
Jon Pratt (NIST MEL)
Tony Schmitz (NIST MEL)

This is a continuing collaboration on projects in high-speed milling and hard turning (turning hardened steels on a lathe) with researchers in MELs Automated Production Technology Division (APTD). The mission of APTD is to fulfill the measurements and standards needs of U.S. discrete-parts manufacturers in mechanical metrology and advanced manufacturing technology.

The high-speed milling work involves the development and application of new models of the dynamic interactions among tool, workpiece, and machine, in order to take full advantage of the material removal capabilities offered by state-of-the-art machines. Such processes are limited more by machine tool chatter than by catastrophic thermal tool failure. In particular, low-immersion cutting strategies that could minimize tool wear as well as provide surface finishes that do not require subsequent costly hand polishing are under investigation.

Traditional machine-tool chatter stability theory involves the study of functional differential equations. A typical practical problem involves the use of Laplace transform methods to map the boundaries in at least a two-dimensional parameter space (e.g., width of cut vs. cutting speed) between stable and unstable response regions for a given system. For very low-immersion cutting, this type of analysis breaks down because the tool is not in contact with the workpiece much of the time. This year, a simple model for low-immersion milling was developed, based on an impact-oscillator model. This has led to a much simpler stability analysis that has been experimentally verified for a specific system.

In a number of industries, including large manufacturers such as Boeing and Caterpillar, work is underway to evaluate the effectiveness of the use of large-scale finite-element software to assist in the prototyping of high-speed machining processes such as hard turning. APTD and MCSD are actively involved in this effort. While considerable progress has been made in the development of predictive models for low-strain-rate manufacturing processes, there is currently a need for improved predictive capabilities for high-rate processes. The accuracy of any model of a large-scale manufacturing operation is limited by how well it can predict the most basic components of the operation. Of these components, chip morphology is certainly the most fundamental, because it provides a direct record of the complex nonlinear plastic material flow process that determines the cutting forces and the temperature along the tool-material interface. These in turn have a dominant effect on tool wear as well as surface finish and subsurface damage of the workpiece.

Material strain hardening was added to the one-dimensional orthogonal cutting model of Davies, Burns, and Evans. It was shown that this could explain the chaotic transition from continuous to shear-localized chip formation that has been observed to take place with increasing cutting speed in a number of materials.

Collaboration with Carol Johnson and Howard Yoon of the Optical Technology Division in the NIST Physics Lab has been re-funded by ATP for FY99-00. This work has involved the development of a device to measure the temperature gradient across the thin region called the primary shear zone where metal cutting takes place in, for example, a hard-turning operation. The work has also involved the development of an experimental setup in MEL for the cutting experiments, and the acquisition and application of a commercial finite-element code by ITL. The software has been helpful in designing the experiments. Ultimately, if the experiments are successful, they will be useful for the validation of any finite-element simulations of high-speed metal-cutting operations.

Geoffrey B. McFadden
Daniel Anderson
Richard Braun
Bruce Murray William Boettinger (NIST MSEL)
John Cahn (NIST MSEL)
Sam Coriell (NIST MSEL)
Bernard Billia (University of Marseille)
Alex Chernov (University Space Research Association)
Robert Sekerka (Carnegie-Mellon University)
Adam Wheeler (University of Southampton)

Mathematical modeling is frequently used to understand and predict the properties of processed materials as a function of the processing conditions by which the materials are formed. During crystal growth of alloys by solidification from the melt, the homogeneity of the solid phase is strongly affected by the prevailing conditions at the solid-liquid interface, both in terms of the geometry of the interface and the arrangements of the local temperature and solute fields near the interface. Instabilities that occur during crystal growth can cause spatial inhomogeneities in the sample that significantly degrade the mechanical and electrical properties of the crystal. Considerable attention has been devoted to understanding and controlling these instabilities, which generally include interfacial and convective modes that are challenging to model by analytical or computational means.

A long-standing collaborative effort between the Mathematical and Computational Sciences Division and the Metallurgy Division has included support from the NASA Microgravity Research Division as well as extensive interactions with university and industrial researchers. In the past year a number of projects have been undertaken that address outstanding issues in materials processing through mathematical modeling. In collaboration with Sam Coriell (855), William Boettinger (855), and Robert Sekerka (Carnegie Mellon University), the dynamics of interfaces in layered geometries for multicomponent materials were studied. These studies are motivated by diffusion problems in thin films and junctions, where the nucleation and growth of additional intermetallic phases can occur during processing. The studies are based on finding similarity solutions that describe the dynamics and geometry of the growing phases, which result in nonlinear equations that describe the interface motion. An interesting outcome of the research is that multiple solutions can be obtained that share the same initial conditions, suggesting that the specific evolution of interfaces that are observed in such systems may be highly sensitive to the details of the system preparation prior to processing.

NIST scientists have been in the forefront of the development of solidification models that feature interfaces that are not sharp, (having zero width), but instead are diffuse with a finite width over which the phase transition occurs. John Cahn (850) pioneered models for the spinodal decomposition of alloys (the Cahn-Hilliard equation) and in the motion of phase boundaries in ordered materials (the Allen-Cahn equation) that are based on such diffuse interface descriptions. Models of this type are of computational as well as theoretical interest, since they can form the basis for numerical schemes that can treat complicated free boundary problems while avoiding the need to track the motion of the interface explicitly. In collaboration with William Boettinger (855), Dan Anderson (George Mason University) and Adam Wheeler (University of Southampton), we have extended such models to include the effects of convection in the melt. These models are being applied to simulate the effects of convection during dendritic growth, where the models capability to describe both convection and changes in interface topology may allow the understanding of grain formation due to the transport of dendrite fragments within the crystal.

Other projects that have been undertaken this year include work with Sam Coriell (855) and Robert Sekerka (CMU) on models of dendritic growth, work with John Cahn (850), Adam Wheeler (University of Southampton), and Richard Braun (University of Delaware) on diffuse interface models of order-disorder transitions, work with Elaine Kim (Stanford University undergraduate) on the effects of surface tension anisotropy on the pinch-off of axisymmetric rods, work with Sam Coriell (855) and Bernard Billia (University of Marseille) on models of Peltier Interface Demarcation, and work with Sam Coriell (855), Bruce Murray (University of Binghamton), and Alex Chernov (University Space Research Associates) on models of step formation during facetted crystal growth.

Michael Donahue
Donald Porter
James Blue
Robert McMichael (NIST MSEL)

The engineering of such IT storage technology as magnetic recording media, GMR sensors for read heads, and magnetic RAM (MRAM) elements requires an understanding of magnetization patterns in magnetic materials at a submicron scale.  Mathematical models are required to interpret measurements at this scale.  The Micromagnetic Modeling Activity Group (muMAG) was formed to address fundamental issues in micromagnetic modeling through two activities: the definition and dissemination of standard problems for testing modeling software, and the development of public domain reference software.  MCSD staff is engaged in both of these activities. Their Object-Oriented MicroMagnetic Framework (OOMMF) software package is a reference implementation of micromagnetic modeling software.  Their achievements in this area since October 1998 include:

• First public beta release of the OOMMF software package


• Publication of the OOMMF User's Guide as NIST IR 6376


• Five additional maintenance and development OOMMF releases


• Over 300 downloads of the OOMMF software package

• Continued collection and dissemination of standard problem results


• Careful analysis of OOMMF results for standard problem #2 revealed inaccuracies, leading to an improved kernel for computing demagnetization fields in development OOMMF releases

• Maintain two e-mail lists, for announcements and discussions


• 168 addresses representing 6 government labs, 20 universities, and 11 companies, including IBM, HP, Quantum, Seagate, ReadRite


• organized and led November 1998 muMAG meeting

• Two invited talks, three conference/workshop presentations, one panel


• Four journal articles

• Redesign of OOMMF extension interface underway to provide simpler means of extending OOMMF with customized solvers


• First example use of new extension interface to be a solver with 3D capabilities suitable for simulation of multilayer structures

Stephen Langer
Edwin Fuller (NIST MSEL)
Andrew Roosen (NIST MSEL)
Craig Carter (MIT)

The OOF Project, a collaboration between MCSD, MSEL's Ceramics Division, MIT, is developing software tools for analyzing real material microstructure.  The microstructure of a material is the (usually) complex ensemble of polycrystalline grains, second phases, cracks, pores, and other features occurring on length scales large compared to atomic sizes.  The goal of OOF is to use data from a micrograph of a real material to compute the macroscopic behavior of the material via finite element analysis.  It was originally designed as a tool for industrial and academic researchers in materials science, but a group at General Electric has proposed using it to monitor the manufactured quality of the ceramic thermal barrier coatings on turbine blades.  GE and NIST received a grant from DOE to develop OOF for this application.  A number of universities have inquired about its possible use as a teaching tool.

In December 1999, OOF was named one of the 25 Technologies of the Year by Industry Week magazine. Other notable events of the last year include:

Many important problems arising in science and engineering are often most conveniently handled by casting them as optimizations, to be solved with numerical algorithms implemented as computer programs. These practical problems frequently require optimization under complex constraints, involve large unmanageable matrices, and/or call for ad hoc procedures. Such pathologies have not yet been systematically analyzed and classified.

We are currently concerned with the development and analysis of algorithms for the solution of such problems as they are encountered at NIST. These specialized and uniquely structured problems of estimation, simulation and control of complex systems have surfaced in a variety of areas such as the modeling of

• ceramics,
• superconductors,
• signal sets for non-Gaussian wireless detectors,
• nonlinear viscoelastic behavior of materials with memory, and
• thin films.

Of particular interest are nonlinear optimization problems that involve computationally intensive function evaluations. The problems are ubiquitous; they arise in simulations with finite elements, in making statistical estimates, or in simply dealing with functions difficult to handle. In many such examples, we have been successful by comparing choices in the implementation of optimization algorithms. In asking, "What makes one formulation for the solution of a problem more desirable than another?" we study the delicate balance among the choices of mathematical approximation, computer architecture, data structures and other factors. For the solution of many applications-driven problems, the proper balance of these factors is crucial.

Bradley Alpert
Leslie Greengard (New York University)
Thomas Hagstrom (University of New Mexico)

Radiation and scattering of acoustic and electromagnetic waves are increasingly modeled using time-domain computational methods, which incrementally advance a solution in time according to the governing differential equations.  This general approach is receiving increasing attention due its promise for modeling wide-band signals, material inhomogeneities, and device nonlinearities.  The applications requiring these capabilities include the design of antennas, low-visibility aircraft, microcircuits, and transducers, nondestructive testing of mechanical devices, and medical and geophysical imaging, among others.

For many of these applications, the accuracy of the computed models is of central importance.  Nevertheless, existing methods typically allow for only limited control over accuracy and cannot achieve high accuracy for reasonable computational cost.  The goal of this project is the development of algorithms and codes for high-accuracy time-domain computations, addressing the key weaknesses of existing methods. These include accurate nonreflecting boundary conditions (that reduce an infinite physical domain to a finite computational domain), suitable geometric representations of scattering objects, and rapidly convergent, stable spatial and temporal discretizations for realistic scatterer geometries.

This project in prior years has already achieved a major advance in applying the exact nonreflecting boundary conditions (which are global in space and time).  An integral equation formulation of the boundary conditions has led to a scheme whose computational cost is O(N log N) in two dimensions and O(N² log N) in three dimensions, for a domain N wavelengths across, as compared with O(N²) and O(N³), respectively, for the interior grid work.

This year another significant advance was achieved, which is expected to eliminate the "small cell" problem for explicit, high-order marching. When a nontrivial scatterer meets a Cartesian discretization, small cells are inevitably created and generally lead to instabilities in explicit time evolution schemes.  Historically, this fact has forced a choice between the undesirable options of implicit time marching and elaborate mesh generation, and sometimes both of these options have been employed to get stability with high-order convergence.  A new integral evolution formula for the wave equation was discovered this year that, quite simply, leads to explicit, high-order discretizations that appear immune to the small cell problem.  An implementation in one spatial dimension has been reported; implementations in two and three dimensions are under development.

Fern Hunt
Antti Pesonen

As part of an exploratory project in bioinformatics funded by the NIST Information Technology Laboratory, Fern Hunt and guest researcher Antti Pesonen have developed a software tool that can be used to investigate statistical and complexity patterns of DNA sequences. The selection of features was motivated firstly by their potential usefulness in answering questions that are frequently addressed in the bioinformatics literature, and secondly by their amenability to graphical display and visualization. Production level sequencing of entire genomes (e.g. bacterial genomes, all 16 chromosomes of yeast) has become routine for simpler organisms, and very rapid progress is being made in the sequencing of the genomes of higher organisms including human beings. These efforts have led to DNA sequences of from several hundred thousand bases for a virus genome, to dozens of millions for a single human chromosome. Consequently, our goal has been to integrate quantitative and visual methods very closely.

As part of an effort to develop tests and to characterize probability models of DNA sequences, the program GenPatterns displays subsequence frequencies and their patterns of recurrence from a sliding window applied to sequence data. Bacterial genomes and chromosome data can be downloaded from GENBANK. A color-coded matrix represents the histogram of subsequence frequencies. The display is based on a tensor product of a two by two matrix based on the four DNA bases A, C, T, G. There are zoom and navigation features that allow one to move through a large data set and remain oriented so that one can investigate the prevalence of specific longer sequences e.g. oligomers (length eight), that are of biological significance.

A great deal of work has been done on modeling DNA sequences as the sample path of a stochastic process. Despite the theoretical difficulty of viewing sequence data as stationary, these models have been fairly successful in gene identification and location of so-called binding sites in mRNA, a sequence quite similar to DNA. GenPatterns has a feature that allows one to compare the model to the data in various ways. A color-coded matrix histogram can be used to visually assess the predicted versus actual subsequence frequencies. There are also provisions for numerical comparison that are under development. The program allows comparison to be made with data and Markov models of arbitrary order. These are expected to be useful in modeling local features of selected parts of the data. There are also features based on the common practice of mapping DNA to paths that are analogous to random walks. This is very useful for, although DNA sequences resemble real random sequences, they differ in significant respects, and this class of tools provides a convenient visual distinction. Quantitatively speaking, this distinction is the basis of methods based on statistical significance and maximum likelihood commonly used in computational biology.

NIST/NBS is known for providing standard reference data in physical sciences and engineering. Less well known is the fact that NIST also supplies reference data in mathematics. The prime example is the NBS Handbook of Mathematical Functions, prepared under the editorship of Milton Abramowitz and Irene Stegun and published in 1964 by the U.S. Government Printing Office. The NBS Handbook is a technical best seller, and likely is the most frequently cited of all technical references. Total sales to date of the government edition exceed 150,000; further sales by commercial publishers are several times higher. Its daily sales rank on amazon.com consistently surpasses other well-known reference books in mathematics, such as Gradshteyn and Ryzhik's Table of Integrals. The number of citations reported by Science Citation Index continues to rise each year, not only in absolute terms but also in proportion to the total number of citations. Some of the citations are in pure and applied mathematics but even more are in physics, engineering, chemistry, statistics, and other disciplines. The main users are practitioners, professors, researchers, and graduate students.

Except for correction of typographical and other errors, no changes have ever been made in the Handbook. This leaves much of the content unsuitable for modern usage, particularly the large tables of function values (over 50% of the pages), the low-precision rational approximations, and the numerical examples that were geared for hand computation. Also, numerous advances in the mathematics, computation, and application of special functions have been made or are in progress. We have begun a project to transform this old classic radically. The Digital Library of Mathematical Functions: A New Web-Based Compendium on Special Functions will be published on the Internet and in a book edition with CD-ROM. The Internet edition will be provided free-of-charge from a NIST Standard Reference Data Web Site. The Web Site and CD-ROM will include capabilities for searching, downloading, and visualization.

Funded by the National Science Foundation and NIST, the DLMF Project is contracting with the best available world experts to rewrite all existing chapters, and to provide additional chapters to cover new functions (such as the Painlevé transcendents) and new methodologies (such as computer algebra). The work is being supervised by four NIST editors (Lozier, Olver, Clark, and Boisvert) and an international board of ten associate editors. The associate editors are

Major achievements since the beginning of FY 1999, are as follows:

• In October 1998 a prototype DLMF website containing a sample chapter on the Airy function written by Frank Olver was released for public access.
• We continue to track developments in MathML, OpenMath, and related technologies. In November 1998, Bruce Miller attended the 11^th OpenMath Workshop at Florida State University. In June, he attended another OpenMath workshop held in Amsterdam. In July, Miller attended TUG99 (TeX Users Group) in Vancouver, Canada.
• In March, a preproposal to the NSF Knowledge and Distributed Intelligence (KDI) program resulted in an invitation to submit a full proposal.
• Also in March, a two-day meeting of the NIST editors and associate editors resulted in a considerable refinement of the chapter list and the identification of tentative authors for about 2/3 of the chapters.
• In May and July, oral presentations were made at conferences and colloquia in Atlanta, Baltimore, Japan, Hong Kong and Edinburgh; two related manuscripts have been submitted for publication. The presentation in Baltimore was made at the IEEE Advances in Digital Libraries Conference, a highly selective conference.
• In August, the full NSF/KDI proposal resulted in the award of $1.3 million for contracting with DLMF authors and validators.
• In September, contracts for 23 chapter outlines were negotiated with tentative authors.
• In December, all 23 chapter outlines were received by the due date.
• In January 2000, another two-day meeting of the full editorial committee resulted in a further refinement of the chapter list, a thorough review of the 23 chapter outlines, the decision to contract further with all the outline authors to write the full chapters, and the identification of tentative authors for most of the remaining chapters.
• Also in January 2000, the DLMF project sponsored an exhibit at the Joint Math Meetings in Washington, DC.

The Fortran 90 bindings for the OpenGL graphics library were developed by MCSD, and have been adopted by the OpenGL Architecture Review Board (ARB) as the official OpenGL Fortran 90 interface.  OpenGL is a software interface for applications to generate interactive 2D and 3D computer graphics. OpenGL is designed to be independent of operating system, window system, and hardware operations, and is supported by many vendors, with products for computing platforms from PCs to supercomputers. The ARB is the governing board of OpenGL, and consists of members from a variety of companies with OpenGL products including ATI, Compaq, Evans & Sutherland, Hewlett-Packard, IBM, Intel, Intergraph, Microsoft, NVIDIA and Silicon Graphics.

In conjunction with this work, Mitchell has developed f90gl, a public domain reference implementation of the Fortran 90 bindings. Since its initial release three years ago, it has been downloaded approximately 5000 times.  Several vendors have begun using f90gl as part of their products or providing access to f90gl from their product web pages, including Absoft, Compaq, Interactive Software Services, Lahey, and N. A. Software.

Highlights for this year include:

• f90gl was updated to Version 1.2 of the OpenGL standard
• support was added for Windows 95/98/NT systems
• support was added for new compilers on Linux systems
• f90gl Version 1.2.0 was released
• Lahey added precompiled f90gl libraries to their Fortran 90 compiler products, and also distributes them on their web site
• Compaq began distributing precompiled f90gl libraries for their Windows compiler product on their web site
• Interactive Software Services used f90gl as a basis for part of their Winteracter product

Ronald Boisvert
Bruce Miller
Marjorie McClain
Roldan Pozo
Karin Remington

MCSD continues to provide Web-based information resources to the computational Science research community. The first of these is the Guide to Available Mathematical Software (GAMS). GAMS is a cross-index and virtual repository of some 9,000 mathematical and statistical software components of use in science and engineering research. It catalogs software, both public domain and commercial, that are supported for use on NIST central computers by ITL, as well as software assets distributed by netlib. While the principal purpose of GAMS is to provide NIST scientists with information on software available to them, the information and software it provides are of great interest to the public at large. GAMS users locate software via several search mechanisms. The most popular of these is the use of the GAMS Problem Classification System. This system provides a tree-structured taxonomy of standard mathematical problems that can be solved by extant software. It has also been adopted for use by major math software library vendors.

A second resource provided by MCSD is the Matrix Market, a visual repository of matrix data used in the comparative study of algorithms and software for numerical linear algebra. The Matrix Market database contains more than 400 sparse matrices from a variety of applications, along with software to compute test matrices in various forms. A convenient system for searching for matrices with particular attributes is provided. The web page for each matrix provides background information, visualizations, and statistics on matrix properties.

This year we purchased a two new Division server systems, both Sun UltraSPARC 60s. Considerable effort was expended in converting our existing setup from SunOS 4.1 to the new Solaris 2 servers. Our main server, math.nist.gov, was placed in the NIST central computing facility on the new external network (outside the new NIST firewall), while the native GAMS database server was placed on a new internal server, math-i.nist.gov. A mirroring facility was set up to automatically all static Division web pages from the internal server to the external server. Finally, a new system for maintaining server logs was developed and implemented.

The Web resources developed by MCSD continue to be among the most popular at NIST. The MCSD Web server at math.nist.gov has serviced more than 20 million Web hits since its inception in 1994 (7 million of which have occurred in the past year!) Altavista has identified more than 5,000 external links to the Division server. GAMS is used more than 10,000 times each month. During a recent 36-month period, 34 prominent research-oriented companies in the .com domain registered more than 100 visits apiece to GAMS. The Matrix Market sees more than 100 users each day. It has distributed more than 16 Gbytes of matrix data, including more than 64,000 matrices, since its inception in 1996.

The utility of these systems is demonstrated by their adoption in other contexts. This year, for example, several new numerical analysis textbooks recommend use of GAMS to their students:

• Ward Cheney and David Kincaid, Numerical Mathematics and Computing, 4^th Edition, Brooks/Cole, Pacific Grove, CA, 1999.
• Curtis F. Gerald and Patrick O. Wheatley, Applied Numerical Analysis, Addison-Wesley, 1999.

Waterloo Maple Inc. is planning to include support for I/O of Matrix Market format matrices in the next release of Maple.

Ronald Boisvert
Bruce Miller
Roldan Pozo
Karin Remington
G.W. Stewart

Java, a network-aware programming language and environment developed by Sun Microsystems, has already made a huge impact on the computing industry. Recently there has been increased interest in the application of Java to high performance scientific computing. MCSD is participating in the Java Grande Forum (JGF), a consortium of companies, universities, and government labs who are working to assess the capabilities of Java in this domain, and to provide community feedback to Sun on steps that should be taken to make Java more suitable for large-scale computing. The JGF is made up of two working groups: the Numerics Working Group and the Concurrency and Applications Working Group. The former is co-chaired by R. Boisvert and R. Pozo of MCSD. Among the institutions participating in the Numerics Working Group are: IBM, Intel, Least Squares Software, NAG, Sun, Visual Numerics, Syracuse University, the University of Karlsruhe, the University of North Carolina, and the University of Tennessee at Knoxville.

This year, MCSD staff presented the findings of the Working Group in a variety of forums, including

• A panel on Java at SC98 in Orlando (November 1998)
• A talk at the Frontiers in Massively Parallel Computing conference (Feb 1999)
• A meeting with Java developers at Sun (March 1999)
• A panel at the ACM Java Grande Conference in San Francisco (June 1999)
• A panel at the JavaOne conference in San Francisico (June 1999)
• A panel at the SIAM National Meeting in Atlanta (July 1999)
• A panel on Java at SC99 in Portland (November 1999)
• A panel on Java at ISCOPE99 in San Francisco (December 1999)

In June 1999, MCSD issued a second report on Working Group recommendations. Comments on these recommendations formed the bulk of a keynote address presented by Bill Joy at the ACM Java Grande Conference in San Francisco later that month. Joy, the developer of Berkeley Unix, co-founder of Sun Microsystems, and co-author of the original Java specification, endorsed the work of the JGF, as well as most of the recommendations of the Numerics Working Group.

Earlier recommendations of the Numerics Working Group were instrumental in the adoption of a fundamental change in the way floating-point numbers are processed in Java. This change will lead to significant speedups to Java code running on Intel microprocessors like the Pentium. All Java programs run in a portable environment called the Java Virtual Machine (JVM). The behavior of the JVM is carefully specified to insure that Java codes produce the same results on all computing platforms. Unfortunately, emulating JVM floating-point operations on the Pentium leads to a four- to ten-fold performance penalty. The Working Group studied an earlier Sun proposal, producing a counter-proposal which was much simpler, more predictable, and which would eliminate the performance penalty on the Pentium. Sun decided to implement the key provision of the Numerics Working Group proposal in Java 1.2, which was released in the spring of 1999.

Tim Lindholm, Distinguished Engineer at Sun, one of the members of the original Java project, the author of The Java Virtual Machine Specification, and currently one of the architects of the Java 2 platform said:

The working group also advised Sun on the specification of elementary functions in Java, which lead to improvements in Java 1.3 which was released in the fall of 1999. The Numerics Working Group has now began work on a series of formal Java Specification Requests for language extensions

Also this year, Roldan Pozo and Bruce Miller developed an interactive numerical benchmark to measure the performance of scientific codes on Java Virtual machines running various platforms. The SciMark 2.0 benchmark includes computational kernels for FFTs, SOR, Monte Carlo integration, sparse matrix multiply, and dense LU factorization, comprising a representative set of computational styles commonly found in numeric applications. Several of SciMark's kernels have been adopted by the benchmarking effort of the Java Grande Forum.

SciMark can be run interactively from Web browsers, or can be downloaded and compiled for stand-alone Java platforms. Full source code is provided. The SciMark 2.0 result is recorded as megaflop rates for the numerical kernels, as well as an aggregate score for the complete benchmark. The current database lists results for over 800 computational platforms, from laptops to high-end servers. As Of January 2000, the record for SciMark 2.0 is over 76 Mflops. We are in the process of adding full applications to expand the SciMark suite.

Finally, G. W. Stewart released the first version of Jampack, a Java package for numerical linear algebra. Jampack provides an alternative design to the JAMA package issued by the MathWorks and NIST last year. While JAMA is designed for the non-expert user, Jampack provides a variety of facilities of interests to experts and others who may want to extend the package. In addition, it supports complex matrices.

Roldan Pozo
William Mitchell

Several years ago, NIST was among some of the first institutions looking into low-cost parallel computing using commodity parts and operating systems. We built several PC clusters using the Linux operating system and fast-ethernet and Myrinet networking technologies. We put real applications on these machines and studied performance/cost trade-offs. The goal was to demonstrate to industry that such configurations were practical computing solutions, not just of interest to the computer science research community. Today, Linux clusters are not only commonplace in industry, but have actually become the dominant product being offered by several hardware vendors.

In conjunction with this effort, William Mitchell has been investigating the best software environments to utilize these architectures. Currently, he has evaluated nearly every Fortran 90/95 Linux compiler available and has conducted extensive benchmarking, reliability, completeness, and cost analysis.

More information on the JazzNet Linux cluster, applications, and available software is available at the project website.

Finite element methods using adaptive refinement and multigrid techniques have been shown to be very efficient for solving partial differential equations on sequential computers.  Adaptive refinement reduces the number of grid points by concentrating the grid in the areas where the action is, and multigrid methods solve the resulting linear systems in an optimal number of operations.  W. Mitchell has been developing a code, PHAML, to apply these methods on parallel computers.  The expertise and software developed in this project are useful for many NIST laboratory programs, including material design, semiconductor device simulation, and the quantum physics of matter.

Much of the advances this year was in the grid-partitioning algorithm.  An adaptively refined grid must be partitioned for distribution over the processors in such a way that the processor load is balanced and communication between processors is minimized.  Mitchell has developed the K-Way Refinement Tree (RTK) partitioning method to quickly find a high quality partition by using information contained in a tree representation of the refinement process.

This work has lead to a collaborative effort with Sandia National Laboratories to develop Zoltan, a dynamic load-balancing library.  Mitchell has designed and implemented a Fortran interface for the C library, and contributed the RTK method.  PHAML has been modified to (optionally) use Zoltan as the grid partitioner, providing an application testbed to compare different load balancing methods.  In addition, PHAML has been enhanced to solve a larger class of problems by adding the capabilities of non-constant coefficients, general boundary conditions, time dependence, nonlinearity, and coupled systems. These allow it to be used to solve application problems in collaboration with NIST scientists.

• completed implementation of RTK in PHAML
• demonstrated that RTK can be an order of magnitude faster than the
• most popular static load balancing library
• extended class of problems solvable by PHAML
• began applying PHAML to a model semiconductor problem
• designed and implemented a Fortran interface for Zoltan
• designed and implemented a refinement tree data structure for Zoltan
• implemented RTK in Zoltan
• interfaced Zoltan with PHAML

One of the most anticipated components of the new BLAS standard is support for sparse matrix computations. Roldan Pozo chairs the Sparse BLAS subcommittee. NIST was first to develop and release a public domain reference implementations for early versions of the standard, which has helped shape the proposal which released for public review this year.

R. Boisvert
J. Conlon
W. Mitchell
(Division Staff)

Division staff members continue to contribute to the high quality scientific computing environment for NIST scientists and engineers via short-term consulting related to mathematics, algorithms and software, and by the support of software libraries on central systems. Division staff maintains a variety of research-grade public-domain math software libraries on the NIST Central Computers (SGI Origins, IBM SP2), as well as for NFS mounting by individual workstations. Among the libraries supported are the NIST Core Math Library (CMLIB), the SLATEC library, the NIST Standards Time Series and Regression Package (STARPAC), and LAPACK. These libraries, as well as a variety of commercial libraries implemented on NIST central systems, are cross-indexed for ease of discovery by NIST staff in the Guide to Available Mathematical Software, along with many other such resources, by MCSD.

This year, we continued our efforts to implementing these libraries on the new NIST SGI Origin 2000 systems (in most cases many versions of the libraries are maintained to support a variety of compilation modes). We also migrated our implementations of CMLIB and LAPACK to ITLs centralized software checkout service to ease the process of mounting libraries on workstations distributed throughout the Institute. This work is supported by the ITL High Performance Systems and Services Division.

NIST has a history of developing some of the most visible object-oriented linear algebra libraries , including Lapack++, Iterative Methods Library (IML++), Sparse Matrix Library (SparseLib++), Matrix/Vector Library (MV++), and most recently the Template Numerical Toolkit (TNT).

TNT incorporates many of the ideas we have explored with previous designs, and includes new techniques that were difficult to support before the ANSI C++ standardization. The library includes support for both C and Fortran array layouts, array sections, basic linear algebra algorithms (LU, Cholesky, QR, and eigenvalues) as well as primitive support for sparse matrices.

TNT has enjoyed several thousand downloads and is currently in use in several industrial applications.

Isabel Beichl
Dianne O'Leary
Francis Sullivan (IDA Center for Computing Sciences)

A central issue in statistical physics is that of evaluating the partition function which describes the probability distribution of states of some system of interest. In a number of important settings, including the Ising model, the q-state Potts model, and the monomer-dimer model, no closed form expressions are known for three-dimensional cases. In addition, obtaining exact solutions of the problems is known to be computationally intractable.

At NIST, related problems occur in the materials science theory group, the combinatorial chemistry working group, and, in physics, models for the Bose-Einstein condensate can be formulated as a dimer problem. 

Many of these computations can be formulated as combinatorial counting problems for which the Monte Carlo Markov Chain (MCMC) method can be formulated to give approximate solutions. In some cases, the Markov Chain is rapidly mixing so that, in principle at least, a pre-specified arbitrary accuracy can be obtained in only a polynomial number of steps. In practice, however, the wall-clock computing time is prohibitively long and hardware bounds on precision can limit accuracy for native mode arithmetic.

A class of probabilistic importance sampling methods has been developed for these problems that appears to be much more effective than the standard MCMC technique for attacking these problems. The key to the approach is the use non-linear iterative methods, such as Sinkhorn balancing, to construct an extremely accurate importance function. Because importance sampling gives unbiased estimates, the importance function can be adjusted so that the simulation spends more time in the more complex regions of state space.

Recent accomplishments include the following.

• Accurate solutions for both the 3-d dimer covering problem and the more general monomer-dimer problem have been obtained. 
• An importance sampling formulation for the 3-d Ising model has been constructed.
• The MCMC method is itself an importance sampling technique. An examination of the relation between it and the new approach leads to an interesting way for collapsing the MCMC random walk to a much smaller number of states having a limit probability distribution that can be readily estimated to high accuracy.

Christoph Witzgall
Javier Bernal
Marjorie McClain
William Stone (BFRL)
G. Choek (BFRL)
Robert Lipman (BFRL)
David Gilsinn (MEL)
J. Lavery (ARO)

Since 1986, C. Witzgall, J. Bernal, and M. McClain, with Witzgall as project leader, have investigated, implemented, and disseminated methods for representing terrain by triangulated surfaces or "TINs" (= Triangulated Irregular Networks). The work utilizes Delaunay triangulations and variations thereof. Part of this work has been supported by the Army Corps of Engineers and by DARPA.

Current work for the Topographic Engineering Laboratory (TEC) of the Army Corps of Engineers is to document editing and "thinning" methods for hydrographic data and corresponding surface generation. Emphasis is on defining the boundaries of sets of data points and identifying areas of missing data.

In 1999, collaboration started with NIST BFRL on applying TIN techniques to LIDAR scans of construction/excavation sites. Such scanning technology is being considered as a component of systems for automatically monitoring construction progress. Witzgall and Bernal are co-authors, together with lead author G.S. Cheok, R.R. Lipman, and W.C. Stone, of the forthcoming "NIST Construction Automation Program Report No. 4: Non-Intrusive Scanning Technology for Construction Status Determination". The challenges encountered were noise abatement and the combination of scan data taken from different viewpoints.

Witzgall is experimenting with methods for screening and filtering noisy scan data and subsequent numerical "registration (coordinate adjustment) for improved coincidence of separate data collections.

It also became apparent that filtering and surface generation should be undertaken in terms of the separate polar coordinate systems centered at the respective scanner locations rather than forming the union of separate data clouds and filtering that combination prior to representing the combined data set by a surface. There is furthermore a need to extend TIN techniques to surfaces which are not "elevated", that is, have a one-to-one projection into a footprint plane, since some surfaces on construction sites can be expected to fall into a more general category. Both of the above tasks require the ability to manipulate and intersect general triangulated surfaces in space. Bernal is developing algorithms for such manipulation based on "tetrahedralization" of data points in space. That technique is also capable of identifying spatial "cut" and "fill" regions and their volumes as defined by the intersection of the prevailing "terrain surface" with a planned "design surface". It is felt that tetrahedralization techniques will attract increasing attention because of their ability to represent proximity relationships in space.

In a separate development, Witzgall and D. Gilsinn (NIST MEL), are collaborating with J. Lavery of the Army Research Office, Durham, about applications to terrain modeling of the nonoscillatory splines pioneered by Lavery.

1. Isabel Beichl, Organizing Committee, The Olga Taussky Todd Celebration of Careers in Mathematics for Women, Berkeley, CA, July 16-18, 1999.
2. R. Boisvert, Program Committee, 1999 ACM Java Grande Conference, San Francisco, CA, June 1999.
3. R. Boisvert, Minisymposium Co-Organizer (with Anne Trefethen, NAG Ltd.), "Java for Numerical Computing", International Congress on Industrial and Applied mathematics, Edinburgh, UK, July, 1999.
4. R. Boisvert, Organizer, Panel on Java for High Performance Computing, SC99, Portland, OR, November 1999.
5. R. Boisvert, Program Committee, IFIP Working Conference on the Architecture of Scientific Software, Ottawa, Canada, October 2000.
6. F. Hunt, Organizing Committee, Workshop onMetrology and Modeling of Color and Appearance, NIST, March 2000.
7. G. McFadden, Organizing Committee, Interfaces for the 21^st Century, Monterey, CA, August 1999.
8. G. McFadden, Co-chair, Organizing Committee, Third SIAM Conference on Mathematical Aspects of Materials Science, Philadelphia, May 2000.
9. MCSD, Co-sponsor, Workshop on Mathematical Problems in Industry, University of Delaware, June 7-11, 1999.
10. R. Pozo, Minisymposium Co-organizer, "Java Numerics Issues", SIAM National Meeting, Atlanta, GA, May 14, 1999.
11. R. Pozo, Program Committee, Workshop on Java for High Performance Computing, ACM International Conference on Supercomputing, Rhodes, Greece, June 19-20, 1999.
12. R. Pozo, Program Committee, Third International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE 99), San Francisco, CA, December 1999.
13. R. Pozo, Program Committee, 2000 ACM Java Grande Conference, San Francisco, CA, June 2000.

Software Released

MCSD staff members enjoy many contacts with colleagues in industry, government, and academia. The purpose of such contacts is quite varied. In some cases, we are providing short-term consulting related to the R&D output of the division. In other cases, an external colleague is providing expertise by participating in a NIST project. The following is an (incomplete) list of institutions with which we have interacted recently.

1. B. Alpert served as a site visitor evaluating research groups funded by the DARPA/NSF program on Optimized Portable Algorithms and Application Libraries (OPAAL).
2. R. Boisvert serves on the ACM Publications Board.
3. R. Boisvert serves as Editor-in-Chief of the ACM Transactions on Mathematical Software.
4. R. Boisvert is a member of the IFIP Working Group 2.5 (Numerical Software).
5. R. Boisvert and R. Pozo co-chair the Numerics Working Group of the Java Grande Forum.
6. M. Donahue and D. Porter serve on the Steering Committee of the muMag Activity Group.
7. D. Lozier serves as Associate Editor of Mathematics of Computation.
8. D. Lozer serves as Chair of the SIAM Activity Group on Orthogonal Polynomials and Special Functions.
9. F. Hunt serves on the Human Resources Advisory Committee of the Mathematical Sciences Research Institute, Berkeley, California.
10. G. McFadden serves as Associate Editor for the SIAM Journal on Applied Mathematics.
11. G. McFadden serves as Associate Editor for the Journal of Computational Physics.
12. G. McFadden serves as Associate Editor for Interfaces and Free Boundaries.
13. R. Pozo chairs the Sparse Subcommittee of the BLAS Technical Forum.
14. B. Saunders serves as treasurer of the MD-DC-VA section of the Mathematical Association of America (MAA).
15. B. Saunders serves on the Selection Committee for the John Smith Award for Distinquished College or University Teaching presented by the MD-DC-VA section of the Mathematical Association of America (MAA).
16. Staff members have refereed articles for the following journals: ACM Transactions on Graphics, ACM Transactions on Mathematical Software, Computing and Visualization, Computing in Science and Engineering, IEEE Transactions on Antennas and Propagation, IEEE Transactions on Magnetics, Interfaces and Free Boundaries, Journal of Applied Physics, Journal of Computational and Applied Mathematics, Journal of Crystal Growth, Parallel Computing, Physica B, Physical Review E, SIAM Journal on Applied Mathematics, SIAM Journal on Optimization, SIAM Journal on Scientific Computing, SIAM Review, Theoretical Computer Science.
17. Staff members reviewed proposals for the following research programs: DOE, NSF KDI Program, NSF Materials Theory Program, NSF Minority Activity Program, NSF SBIR Program, and other NSF programs

MCSD staff members engage in a variety of activities designed to promote careers in mathematics and computational science. Among these are the following.

1. Isabel Beichl served on a panel on Women in Mathematics at the Association for Women in Mathematics Meeting in January 1999.
2. Isabel Beichl, Fern Hunt, and Bonita Saunders hosted a visit to NIST by students from the George Washington University Summer Program for Women on July 23, 1999.
3. An interview with Ron Boisvert is featured in the "A Day in the Life of " website maintained by Crossroads, the ACM student publication. The site provides insight for students regarding careers in computer science.
4. Ron Boisvert served as a judge for the Science Expo of the Neelsville Middle School in Gaithersburg.
5. Tony Kearsley serves as a mentor for two African-American women graduate students through the SIAM Graduate Student Mentoring Program.
6. Tony Kearsley co-organized (with Monica Matrinez-Carnales of Stanford) a DOE-sponsored session on "Simulation in Science and Engineering" which was videotaped for use in classroom settings to encourage women and under-represented minorities to study science.
7. Fern Hunt and Bonita Saunders served on a panel on Mathematics in the Biological Sciences for Mathematics Awareness Month at Morgan State University in Baltimore in April 1999.
8. Bonita Saunders submitted an update of her career profile for the second edition of the MAA publication 101 Careers in Mathematics.
9. Bonita Saunders assisted a fourth grade teacher at Brown Station Elementary School in Gaithersburg in teaching math skills to underachieving students.
10. Marjorie McClain serves as a math tutor for Gaithersburg High School.
11. MCSD staff mentored student employees from the following institutions: Carnegie-Mellon University, Montgomery Blair High School, Montgomery College, and Quince Orchard High School.

MCSD receives a variety of funding to supplement the base STRS allocation obtained from the NIST Information Technology Laboratory. Funding for fiscal year 1999 includes the following. (For joint funding, the amount shown is MCSDs portion.)

1. B. Alpert (joint with NYU), Time Domain Modeling Algorithms, DARPA, $174K.
2. R. Boisvert (joint with the University of Tennessee at Knoxville and Bell Labs), Evolving Software Repositories, DARPA, $110K.
3. G. McFadden (joint with NIST Materials Science and Engineering Lab), Investigation of Flow Effects during Directional Solidification and Dendritic Growth, NASA, $91K.
4. W. Mitchell, Mesh Generation and Adaptive Refinement, Sandia National Laboratory, $60K.
5. C. Witzgall, Thinning of Subaquatic Depth Measurements, Army Corps of Engineers, $32K.
6. D. Lozier and B. Fabijonas (joint with the Russian Academy of Sciences), Numerical Software for Mathematical Special Functions, U.S. Civilian Research and Development Foundation for the Independent States of the Former Soviet Union (CRDF), $11K.
7. D. Lozier, F. Olver, C. Clark (PL), and R. Boisvert, Mathematical Foundations for a Networked Scientific Knowledge Base, National Science Foundation, $1300K (3-year funding).

1. D. Lozier and R. Boisvert, Digital Library of Mathematical Functions, Systems Integration for Manufacturing Applications Program, NIST Manufacturing Engineering Laboratory, $100K.
2. F. Hunt (joint with NIST Building and Fire Research Lab, NIST Physics Lab and NIST Manufacturing Engineering Lab), Advanced Methods and Models for Optical Reflectance and Scattering, NIST Competency Fund, $82K.
3. D. Lozier and M. McClain, Adaptive Learning Module for Mathematical Functions, NIST Advanced Technology Program, $53K.
4. Kearsley (joint with ITL Advanced Networking Technologies Division and the NIST Electronics and Electrical Engineering Lab), Wireless Communications, NIST Competency Fund, $51K.
5. Alpert and A. OGallagher (joint with NIST Electronics and Electrical Engineering Lab and ITL High Performance Systems and Services Division), Rigorous Modeling of Optoelectronic Components for Manufacturing, NIST Advanced Technology Program, $48K.
6. Witzgall (joint with ITL Statistical Engineering Division), Bayesian Statistics in Metrology, NIST Competency Fund, $41K.
7. Lozier, Digital Library of Mathematical Functions, NIST Standard Reference Data Program, $40K.
8. B. Miller and M. McClain, Life-cycle Energy and Water Conservation Software in Java, NIST Building and Fire Research Laboratory, $28K.
9. T. Burns (joint with NIST Manufacturing Engineering Laboratory), Machining Process Metrology and Simulation, NIST Advanced Technology Program, $25K.
10. G. McFadden (joint with NIST Materials Science and Engineering Laboratory), Residual Stresses in Ceramic Materials, NIST Advanced Technology Program, $20K.

Other ITL Programs

1. R. Boisvert et al., Math Software Support, ITL High Performance Systems and Services Division (Supercomputing Funding), $425K.
2. J. Blue et al., Math Modeling Support, ITL High Performance Systems and Services Division (Supercomputing Funding), $300K.
3. I. Beichl and F. Hunt, Stochastic Approaches in Bioinformatics, ITL Pre-competency Fund, $100K.

Left: Abbie OGallagher of MCSD-Boulder. Right: Roldan Pozo and a Jazznet PC cluster.

MCSD consists of full time permanent staff located at NIST laboratories in both Gaithersburg, MD and Boulder, CO. This is supplemented with a variety of faculty appointments, guest researchers, postdoctoral appointments, and student appointments. The following list reflects the status at the end of FY1999.

Legend: F = Faculty Appointee, GR = Guest Researcher, PD = Postdoctoral Appointee, S = Student, PT= Part time