A Program of Research to Support the Analysis and Simulation of Physical Systems

Table of Contents:

  1. Principal Investigator.
  2. Productivity Measures.
  3. Summary of Objectives and Approach.
  4. Detailed Summary of Technical Progress.
  5. Transitions and DOD Interactions.
  6. Software and Hardware Prototypes.
  7. List of Publications.
  8. Invited and Contributed Presentations.
  9. Honors, Prizes or Awards Received.
  10. Project Personnel Promotions.
  11. Project Staff.
  12. Multimedia URL.
  13. Keywords.
  14. Business Office.
  15. Expenditures.
  16. Students.
  17. Book Plans.
  18. Sabbatical Plans.
  19. Related Research.
  20. History.

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

  1. Enable scientists and engineers to exchange, store, index and manipulate mathematical expressions and mathematically based models as easily as is now the case with textual data.
  2. Permit scientists and engineers to describe simulations and mathematical analyses using familiar concepts from mathematics and physics (e.g., partial differential equations) rather than directly using traditional programming languages such as Fortran or C.
  3. Automate the transformation of these high level specifications into efficient computational codes for sequential and parallel machines.
  4. Approach: Integrate the technologies of geometric modeling, symbolic mathematics, numerical analysis, compilation/code generation, and formal methods to create a new methodology and environment for engineering analysis and simulation. These technologies have all been used before to attack engineering analysis problems, but used in isolation. They are far more potent when used in concert within a single integrated environment. The three components of this approach are:

Detailed Summary of Technical Progress.

  1. Integrated the tools developed for geometric analysis (mesh generation) and topological analysis with our existing tools for symbolic computation. Groundwork has been laid for integration with logical inference tools (Nuprl, KQML, etc.) and initial experiments are underway with Nuprl. Manual has been prepared and initial release has been made available on the Internet.
  2. Refined and extended SPL, our very high-level mathematical specification language for scientific computing. Geometric and topological structures have been incorporated into the language. Transforms for variety of different tasks have now been developed for SPL, e.g., finite element analyses, initial value problems and matrix code. Generation of production code for simulations will be undertaken this coming year.
  3. Developed prgram transformations for general weighted residual methods. This yielded a simple tool for generating finite element analyses that even works for non-linear partial differential equations.
  4. As part of the MADEFAST demo, used Weyl to translate between formats of two different packages -- Alpha1 (a geometric modeler) and PLTMG (a finite element package)-- and used Weyl to produce more appropriate triangulations for simulation.

Transitions and DOD Interactions.

  1. With the current release of Weyl, we have just begun our transition activities. Earlier, other researchers at Cornell, Harris Corp. and George-Mason University have used prototype versions of system for research purposes. In all of these cases, the flexibility provided by Weyl permitted the researchers to code computations more succinctly, and, in some cases, with fewer errors than previous attempts.
  2. Our current system (our mathematical substrate Weyl combined with our tools for topological analysis and for guaranteed-quality mesh generation) is available over the Internet (see http://www.cs.cornell.edu/Info/Projects/SimLab/index.html). In its current form, its most appropriate use is by researchers, and we expect most of its use to be by academic researchers. There are two ways in which we are trying to gauge the impact of our work. First, we will evaluate how effective Weyl is in enhancing the computational prowess of systems developed outside of Cornell. Second, we will evaluate the impact of our architectures and ideas on industrial products. Already, we have attracted the interest of a number of companies (Microsoft, Apple, NAG, etc.) and initial discussions are underway.

Software and Hardware Prototypes.

  1. Prototype Name: SimLab R1 Release

List of Publications.

  1. M. Bern, L. P. Chew, D. Eppstein, and J. Ruppert, ``Dihedral Bounds for Mesh Generation in High Dimensions,'' Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (1995), pp. 189-196.
  2. L. P. Chew, K. Kedem, M. Sharir, B. Tagansky, and E. Welzl, ``Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions,'' Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (1995), pp. 197--204.
  3. L. P. Chew, D. Dor, A. Efrat, and K. Kedem, ``Geometric Pattern Matching in d-Dimensional Space,'' Proceedings of the European Symposium on Algorithms (1995), pp. 264-279.
  4. R. Constable, ``Experience using type theory as a foundation for computer science,'' Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science (1995), pp. 266-279.
  5. D. Dean and R. Zippel, ``Matching Data Storage to Application Needs,'' Operating Systems Review, vol. 29, no. 1, January 1995, pp. 68-73.
  6. P. B. Jackson, Enhancing the Nuprl Proof Development System and Applying it to Computational Abstract Algebra, Ph.D. Thesis, Dept. of Computer Science, Cornell University, January 1995. http://cs-tr.cs.cornell.edu:80/TR/CORNELLCS:TR95-1509
  7. P. B. Jackson, ``Exploring Abstract Algebra in Constructive Type Theory,'' CADE12, Lecture Notes in Artificial Intelligence, Springer-Verlag, July 1994.
  8. D. Kozen, S. Landau and R. Zippel, ``Decomposition of Algebraic Functions,'' Algorithmic Number Theory, Lecture Notes in Computer Science 877, Springer-Verlag, 1995, pp. 80-92.
  9. C. Mannion and S. Allen, ``A Notation for Computer Aided Mathematics,'' Computer Science Tech. Report 94-1465, Cornell University, February, 1995. http://cs-tr.cs.cornell.edu:80/TR/CORNELLCS:TR94-1465
  10. R. Rubinfeld and R. Zippel, ``A New Modular Interpolation Algorithm for Factoring Multivariate Polynomials,'' Algorithmic Number Theory, Lecture Notes in Computer Science 877, Springer-Verlag, 1995, pp. 93-107.
  11. R. Zippel, ``A constraint-based scientific programming language,'' Principles and Practice of Constraint Programming -- The Newport Papers, (Editors: V. Saraswat and P. Van Hentenryck), MIT Press (1995), pp. 115-130.

Invited and Contributed Presentations.

  1. Automatic generation of engineering analysis tools, ARPA MADE PI Meeting, Salt Lake City, November 9, 1994. Richard Zippel.
  2. Program transforms for mathematical computation, ARPA MADE PI Meeting, Salt Lake City, November 10, 1994. Richard Zippel.
  3. Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions, Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1995. Paul Chew.
  4. Dihedral Bounds for Mesh Generation in High Dimensions, Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1995. David Eppstein.
  5. Program transforms for mathematical computation, Dept. of Mathematics, Florida State University, Tallahassee, Florida, February 20, 1995. Richard Zippel.
  6. Program transforms for mathematical computation, International Conference on High Performance Computing, Baton Rouge, Louisiana, February 24, 1995. Richard Zippel.
  7. Experience using type theory as a foundation for computer science, 10th Annual IEEE Symposium on Logic in Computer Science, San Diego, June 1995. Robert Constable.
  8. Program Transformations for Scientific Computing. ARPA PI Meeting, Stanford University, Palo Alto, California, July 12, 1995. Richard Zippel.
  9. Program Transformations for Scientific Computing. Xerox Webster Research Lab, Webster, NY, August 2, 1995. Richard Zippel.
  10. Program Transformations for Scientific Computing. Microsoft Research Center, Redmond, Washington, August 11, 1995. Richard Zippel.
  11. Simulation Support for Collaborative Design. ARPA SISTO Symposium, Washington, DC, August 30, 1995. Richard Zippel.
  12. Geometric Pattern Matching in d-Dimensional Space, Ionian Vision/Geometry Workshop, Corfu, Greece, September 1995. Paul Chew.
  13. Geometric Pattern Matching in d-Dimensional Space, European Symposium on Algorithms (ESA '95), Corfu, Greece, September 1995. Alon Efrat.

Honors, Prizes or Awards Received.

Project Personnel Promotions.

Project Staff.

  1. Name: Dr John E. Hopcroft
  2. Name: Dr Robert Constable
  3. Name: Dr Paul Chew
  4. Name: Dr Richard Zippel
  5. Name: Dr Rick Palmer
  6. Name: Dr Paul Jackson
  7. Name: Dr Todd Wilson
  8. Name: Dr Andreas Weber

Multimedia URL.

  1.  
  2. EOYL FY95
  3. QUAD FY95
  4. EOYL FY94
  5. The SimLab Home Page. The home page for our project.
  6. New Directions in Systems Research. Richard Zippel's slide presentation on some new ideas on how systems research should proceed. Includes brief discussions of non-contemporaneous communications, microstorage architecture, and program transformations.
  7. Chew's Mesher in Action. A simple animation (using Postscript) of the mesher at work. The colors represent grades for the various triangles: red implies bad shape, yellow implies too large, blue implies boundary is too long, and green implies all right.
  8. Additional Mesh Generation Research at Cornell. The QMG mesh generation pacakge developed by Steve Vavasis.
  9. Web Resources for Finite Element Mesh Generation. Mesh generation work from all over the world. Maintained by Robert Schneiders.
  10. MADE Project Home Page. The home page for the ARPA-MADE (Manufacturing Automation and Design Engineering) program that helps fund us.

Keywords.

  1. Automated Simulation and Analysis
  2. Computer Algebra
  3. Guaranteed Quality Mesh Generation
  4. Problem Solving Environments
  5. Chain Models

Business Office

Expenditures

  1. Est. FY96: 100%
  2. FY95: 100%
  3. FY94: 100%
  4. FY93: 100%

Students

Book Plans

Sabbatical Plans

  1. Person: Robert Constable

Related Research

  1.  
  2. Additional Mesh Generation Research at Cornell. The QMG mesh generation pacakge developed by Steve Vavasis.
  3. Web Resources for Finite Element Mesh Generation. Mesh generation work from all over the world. Maintained by Robert Schneiders.
  4. MADE Project Home Page. The home page for the ARPA-MADE (Manufacturing Automation and Design Engineering) program that helps fund us.

History