A Program of Research to Support the Analysis and Simulation
of Physical Systems 
Table of Contents:
    - Principal Investigator.
    
- Productivity Measures.
    
- Summary of Objectives and
        Approach. 
- Detailed Summary of
        Technical Progress. 
- Transitions and DOD
        Interactions. 
- Software and Hardware
        Prototypes. 
- List of Publications.
    
- Invited and Contributed
        Presentations. 
- Honors, Prizes or Awards
        Received. 
- Project personnel
        promotions obtained. 
- Project Staff. 
- Misc Hypermedia URL.
    
- Keywords. 
Principal
Investigator.
    - PI Name: John E. Hopcroft 
- PI Institution: Cornell University 
- PI Phone Number: 607/255-6087 
- PI Fax Number: 607/255-4428 
- PI E-mail Address:
        John_Hopcroft@qmengr.cornell.edu 
- PI URL Home Page: http://www.cs.cornell.edu/Info/Faculty/John_Hopcroft.html
    
- Grant Title: A Program of Research to
        Support the Analysis and Simulation of Physical Systems 
- Grant/Contract Number: N00014-92-J-1839 
- R&T Number: 433301- - -09 
- Reporting Period:01 Oct 93 - 30 Sep 94 
Productivity
Measures.
    - Number of refereed papers submitted not yet published:
        1 
- Number of refereed papers published: 1 
- Number of unrefereed reports and articles: 16 
- Number of books or parts thereof submitted but not
        published: 1 
- Number of books or parts thereof published: 1 
- Number of project presentations: 2 
- Number of patents filed but not yet granted: 0 
- Number of patents granted and software copyrights:
        0 
- Number of graduate students supported >= 25% of
        full time: 4 
- Number of post-docs supported >= 25% of full time:
        2 
- Number of minorities supported: 0 
Summary of
Objectives and Approach.
    - 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. 
- 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. 
            - Automate techniques for generating the equations
                that govern the behavior of physical systems.
                This includes physical element and variational
                techniques. 
- 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. 
- 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.
    - 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. 
- 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. 
- 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.
    - 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. 
- 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). 
- 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.
    - 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. 
- The
        Vista Microstorage Architecture A flexible interface
        to storage and a smooth transition from traditional file
        systems to more powerful object oriented storage models. 
- The
        SPL/Weyl Scientific Programming Language 
- The
        Guaranteed Quality Mesher Software for creating
        guaranteed quality triangulations of two dimensional flat
        and curved surfaces. 
- 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.
    - 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. 
- 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. 
- 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. 
- 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. 
- 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. 
- B. Donald, J. Jennings and D. Rus, ``Information
        Invariants for Cooperating Autonomous Mobile Robots,''
        Proceedings of the International Symposium on Robotics
        Research, October 1993. 
- M. L. Fredman and M. Rauch, ``Lower Bounds for Dynamic
        Connectivity Problems in Graphs,'' Cornell Computer
        Science Tech. Report 94-1420, April 1994. 
- 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. 
- 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 
- 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.) 
- R. Palmer and V. Shapiro. ``Chain Models of Physical
        Behavior for Engineering Analysis and Design,'' in
        Research in Engineering Design, Springer-Verlag, Spring
        1994. 
- R. Palmer. ``Chain Models and Finite Element Analysis,''
        Cornell Computer Science Tech. Report 94--1406, January
        1994. 
- M. Rauch. ``Improved Data Structures for Fully Dynamic
        Biconnectivity,'' Proceedings of the 26th Annual
        Symposium on Theory of Computing, 1994, pp. 686--695. 
- 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. 
- 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. 
- D. Rus and D. Subramanian. ``Modular architectures for
        information agents,'' Proceedings of the AAAI Symposium
        on Intelligent Software Agents, March 1994. pp. 79-86. 
- 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. 
- R. Zippel. Effective Polynomial Computation, Kluwer
        Academic Publishers, 1993, 363 pages. 
- 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.
    - 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. 
- Chain Models: Towards a Computer Language for Physical
        Systems, The Third SIAM Conference on Geometric Design,
        Tempe, Arizona, November, 1993. Rick Palmer. 
- Triangular Meshes and Curved Surfaces, University of
        Toronto, Toronto, Ontario, May 1994. Paul Chew. 
- Understanding 3D Voronoi Diagrams, AFOSR Review,
        Wright-Patterson AFB, Dayton, Ohio, May 1994. Paul Chew. 
- 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.
    - John
        E. Hopcroft - Joseph Silbert Dean of Engineering, PI 
- Robert
        Constable - Professor, PI 
- Paul
        Chew - Senior Research Associate 
- Richard
        Zippel - Senior Research Associate 
- Paul
        Jackson - Research Associate 
- Sekhar
        V. Muddana - Research Associate 
- Rick
        Palmer - Research Associate 
- Daniela
        Rus - Research Associate 
- Todd
        Wilson - Research Associate 
- Dawson
        Dean Graduate Student 
- Scott
        Mardis - Graduate Student 
- Divakar
        M. Viswanath - Graduate Student 
- David
        Dunham - Undergraduate 
- Todd Wheeler -
        Undergraduate 
Misc
Hypermedia.
    - SimLab Home Page 
Keywords.
    - Automated Simulation and Analysis 
- Computer Algebra 
- Guaranteed Quality Mesh Generation 
- Problem Solving Environments 
- Chain Models 
    Rick Palmer / rick@cs.cornell.edu