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 obtained.
  11. Project Staff.
  12. Misc Hypermedia URL.
  13. Keywords.

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

  1. OBJECTIVES: Enable scientists and engineers to construct, modify, and evaluate simulations and other engineering analyses by creating an environment that permits these processes to be described at an appropriate and natural semantic level --- a user describes an engineering analysis using familiar concepts from mathematics and physics rather than directly using traditional programming languages such as Fortran or C. Automate the transformation of PDEs into high-level computational schemes. Develop the tools to convert these computational schemes into efficient codes for sequential and parallel machines.
  2. 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. Three major components of this approach are discussed below.
    1. Automate techniques for generating the equations that govern the behavior of physical systems. This includes physical element and variational techniques.
    2. Develop a language for describing engineering analysis problems based on the natural mathematical and physical concepts of the problem, e.g. differential equations, minimization principles and geometric and topological objects.
    3. Develop transformation techniques that convert this language into efficient executable code on a variety of different architectures, both sequential and parallel. These re-usable transformations capture mathematical analysis techniques and make them applicable to a wider range of code generation tasks than other approaches. Of particular interest are techniques for meshing geometric objects, discretizing ordinary and partial differential equations and code optimization.

Detailed Summary of Technical Progress.

  1. Refined and extended SPL, our very high-level language for scientific computing. Within SPL, a user expresses computations in terms of continuous constraints (e.g., differential equations). Geometric and topological structures have been incorporated into Weyl, our symbolic algebra substrate for SPL. The transform library has been significantly expanded, and mechanisms have been provided to simplify the specification of transformations.
  2. Developed and implemented the first prototype of a microstorage architecture, a ``microkernel'' storage system that facilitates the implementation of different storage models (such as file systems, object oriented databases and continuous media storage systems). By using a microstorage architecture multiple storage models can co-exist, data can be viewed and manipulated by more than one storage model and storage structures can span multiple machines. This organization provides support for portability of storage models, for high performance and for the continued use legacy software systems even while modern storage architectures are being phased in.
  3. Improved techniques for the creation of guaranteed-quality triangular meshes for curved surfaces. Developed new analysis techniques for 3D generalizations of 2D mesh data-structures.

Transitions and DOD Interactions.

  1. We have been working with GE and Xerox to transfer our analysis and simulator generation technology to industrial use. We have developed a plan to create a prototyping environment for design, called PROTOLAB, that is intended to provide an easy-to-use environment for creating electro-mechanical parts and assemblies.
  2. With James Cremer at the University of Iowa, we have been working to apply our tools and methodology to the development of real-time (or near real-time) simulation of the dynamics of an automobile for comparison with (and perhaps eventual incorporation in) the Iowa Driving Simulator project, a person-in-the-loop simulator with military and civilian applications. For further information about the above two activities, contact Rick Palmer (rick@cs.cornell.edu).
  3. Weyl, our computer algebra substrate is being actively used by researchers in commutative algebra at George Mason University (and here at Cornell), and for problems in coding theory at the Supercomputing Research Center. In addition, copies of Weyl have been requested by over a dozen other sites for investigation. Weyl's unique flexibility, the generality of its algorithms and the ease of incorporating its symbolic abilities in existing programs are the major reasons for its use. Questions regarding Weyl should be directed to Richard Zippel (rz@cs.cornell.edu).

Software and Hardware Prototypes.

  1. The Chains Algebraic-Topological Programming Language A prototype system for programming scientific software based on a computer implementation of cells, cell complexes, chains, and the boundary and coboundary operators.
  2. The Vista Microstorage Architecture A flexible interface to storage and a smooth transition from traditional file systems to more powerful object oriented storage models.
  3. The SPL/Weyl Scientific Programming Language
  4. The Guaranteed Quality Mesher Software for creating guaranteed quality triangulations of two dimensional flat and curved surfaces.
  5. Lisp-HTML interface. A quick (and fairly dirty) interface for allowing LISP to serve HTML documents -- uses CGI with a socket interface. This is used in the Mesher and Chains interfaces.

List of Publications.

  1. J. Allan, J. Davis, D. Krafft, D. Rus and D. Subramanian. ``Information Agents for Building Hyperlinks,'' Proceedings of the CIKM Workshop on Intelligent Hypertext, November 1993. pp. 41-46.
  2. D. Dean and R. Zippel. ``Implementing File Systems and a Object Databases in a Microstorage Architecture,'' Cornell Computer Science Tech. Report 93-1393, October 1993.
  3. D. Dean and R. Zippel. ``Vista: A Microstorage Architecture that Implements File Systems and Object Databases,'' International Workshop on Object Oriented Operating Systems, December 1993. pp. 194--198.
  4. B. Donald, J. Jennings and D. Rus, ``Analyzing Teams of Cooperative Mobile Robots,'' Proceedings of the 1994 International Conference on Robotics and Automation, pp. 1896-1903.
  5. B. Donald, J. Jennings and D. Rus, ``Information Invariants for Distributed Manipulation,'' The First Workshop on the Algorithmic Foundations of Robotics, A. K. Peters, Boston, MA ed. R. Wilson and J.-C. Latombe, February 1994.
  6. B. Donald, J. Jennings and D. Rus, ``Information Invariants for Cooperating Autonomous Mobile Robots,'' Proceedings of the International Symposium on Robotics Research, October 1993.
  7. M. L. Fredman and M. Rauch, ``Lower Bounds for Dynamic Connectivity Problems in Graphs,'' Cornell Computer Science Tech. Report 94-1420, April 1994.
  8. J. Jennings and D. Rus, ``Active Model Acquisition for Near-Sensorless Manipulation with Mobile Robots,'' Proceedings of the IASTED International Conference on Robotics and Manufacturing, September 1993. pp. 179-184.
  9. P. Klein, S. Rao, M. Rauch, and S. Subramanian, ``Faster Shortest-Path Algorithms for Planar Graphs,'' Proceedings of the 26th Annual Symposium on Theory of Computing, 1994, pp. 27--37
  10. D. Kozen, S. Landau, R. Zippel. ``Decomposition of Algebraic Functions,'' Algebra and Number Theory '94, Springer Lecture Notes in Computer Science, 1994. (also Computer Science Tech. Report 94--1410.)
  11. R. Palmer and V. Shapiro. ``Chain Models of Physical Behavior for Engineering Analysis and Design,'' in Research in Engineering Design, Springer-Verlag, Spring 1994.
  12. R. Palmer. ``Chain Models and Finite Element Analysis,'' Cornell Computer Science Tech. Report 94--1406, January 1994.
  13. M. Rauch. ``Improved Data Structures for Fully Dynamic Biconnectivity,'' Proceedings of the 26th Annual Symposium on Theory of Computing, 1994, pp. 686--695.
  14. D. Rus. ``Coordinated Manipulation of Polygonal Objects,'' Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems}, July 1993. pp. 106-112.
  15. D. Rus. and K. Summers. ``Using Whitespace for Automated Document Sharing,'' Proceedings of the 1994 International Workshop on Principles of Document Processing, 1994. pp. 1-25.
  16. D. Rus and D. Subramanian. ``Modular architectures for information agents,'' Proceedings of the AAAI Symposium on Intelligent Software Agents, March 1994. pp. 79-86.
  17. D. Rus and D. Subramanian. ``Multi-media RISSC Informatics: Retrieving Information with Simple Structural Components,'' Proceedings of the International Conference on Information Knowledge Management, November 1993. pp. 283-294.
  18. R. Zippel. Effective Polynomial Computation, Kluwer Academic Publishers, 1993, 363 pages.
  19. R. Zippel. ``Systems Research in the Age of On-line Coffee Houses,'' Cornell Computer Science Tech. Report 94-1419. April 1994.

Invited and Contributed Presentations.

  1. Fast Computation of the Minimum Symmetric Difference for Convex Shapes, Army Research Office and MSI Stony Brook Workshop on Computational Geometry, Raleigh, North Carolina, October 1993. Paul Chew.
  2. Chain Models: Towards a Computer Language for Physical Systems, The Third SIAM Conference on Geometric Design, Tempe, Arizona, November, 1993. Rick Palmer.
  3. Triangular Meshes and Curved Surfaces, University of Toronto, Toronto, Ontario, May 1994. Paul Chew.
  4. Understanding 3D Voronoi Diagrams, AFOSR Review, Wright-Patterson AFB, Dayton, Ohio, May 1994. Paul Chew.
  5. Physical Elements: Using chains and cell complexes to solve multiple domain PDE problems, The 14th IMACS World Congress, Atlanta, Georgia, July, 1994. Rick Palmer.

Honors, Prizes or Awards Received.

Project Personnel Promotions Obtained.

Project Staff.

  1. John E. Hopcroft - Joseph Silbert Dean of Engineering, PI
  2. Robert Constable - Professor, PI
  3. Paul Chew - Senior Research Associate
  4. Richard Zippel - Senior Research Associate
  5. Paul Jackson - Research Associate
  6. Sekhar V. Muddana - Research Associate
  7. Rick Palmer - Research Associate
  8. Daniela Rus - Research Associate
  9. Todd Wilson - Research Associate
  10. Dawson Dean Graduate Student
  11. Scott Mardis - Graduate Student
  12. Divakar M. Viswanath - Graduate Student
  13. David Dunham - Undergraduate
  14. Todd Wheeler - Undergraduate

Misc Hypermedia.

  1. SimLab Home Page

Keywords.

  1. Automated Simulation and Analysis
  2. Computer Algebra
  3. Guaranteed Quality Mesh Generation
  4. Problem Solving Environments
  5. Chain Models
Rick Palmer / rick@cs.cornell.edu