Developing an Approach to the Analytic Gap: Advanced Mathematics for Scale and Complexity : Developing an Approach to the Analytic Gap: Advanced Mathematics for Scale and Complexity Dr. Kirstie Bellman, Co-PI
(Partner Shankar Sastry, UCB)
Aerospace Integration Science Center, The Aerospace Corporation March 16, 2006
Overview : Overview
Description of Current Analytic Gap Project
Background
The Needs: Vast Networks, People and Technical Systems, Embedded systems
Lack of Sufficient Analytic Methods for Very Large Complex Systems
Mathematical, computational, and modeling needs
Current Goals of study: what constitutes success
Map DoD operational deficits to potentially important mathematical R&D
Identify new approaches for evaluating the scalability of methods
Current Organization of Study
Recap of History : Recap of History At January 26, 2005 OSD/NII meeting, we discussed several large systems issues, with a special emphasis on the disturbing “analytic gap”
Insufficient methods for handling the scale of current large complex systems, undermining sensor, data, and networking capabilities
Insufficient methods for evaluating mathematical or computational capabilities and matching to appropriate problems and data sets
Asst SecDef, NII requested we return with approach for going forward; we developed the following study plan.
Approach for Closing the Gap : Approach for Closing the Gap Rapid , small assessment study with two expert panels:
Reality check on DoD scale problems: Where is DoD hardest hit by lacking sufficient analytic methods for very large systems? What problems are not being addressed? How does DoD currently work around problems of scale?
Advanced Mathematics for Problems in Scale and Complexity: Develop better methods to handle large complex systems; develop better methods for reasoning about the limitations of mathematical and computational approaches. Develop better evaluation techniques that can compare computational methods and ‘certify’ tools.
Challenge Problems: Panel 3 would combine the results of Panels 1 and 2 to create a set of challenge problems that would be used by funding agencies to develop programs addressing gap, and possibly as benchmarks for comparisons among computational methods.
Panel One: How damaging is this problem? : Panel One: How damaging is this problem? Goal of Panel: Assess where problems of scale are causing the most problems within DoD. Assess how DoD is currently working around problems of complexity and scale.
Outcomes of benefit to OSD:
Focus on most critical and/or damaging parts of the analytic gap first;
Obtain realistic assessment of what questions are not being addressed because of gap;
Better planning for both current and future systems.
Panel 1 Examples of Needs : Panel 1 Examples of Needs Multi- and Dynamic Criteria Optimization
Even single-criterion optimization limited computationally to < 200K nodes (NPS example)
Tracking methods for evaluating the impact of changing specifications or not better specifying systems
Ariane IV worked well. Moving Ariane IV IRU into the Ariane V caused a billion dollar failure. Requirements deceptively similar
Waste of data we are currently unable to analyze
Current Needs:
Massive Networks, e.g. GIG
Design/control of Embedded Devices
Identifying relevant data amid massive amounts of data
Modeling of humans as part of complex systems, e.g. social networks, human cognition, culture
Panel 2: Advanced Mathematics for Problems in Scale and Complexity : Panel 2: Advanced Mathematics for Problems in Scale and Complexity Goals of Panel:
Identify potential R&D projects for immediate and long-term gains on closing analytic gap.
Understand the trade-offs among modeling, mathematical and computational methods
Develop roadmap for creating methods supporting systematic test and analysis of computational methods
Outcomes of benefit to OSD:
Provide DoD decision-makers with specifications and justification for better informed purchase of mathematical and computational methods.
Address top priority analytic needs for current design decisions and ongoing operational examples
Panel 2 –One Major Goal is More Mathematics About Scalability: Beyond NP-Complete : Panel 2 –One Major Goal is More Mathematics About Scalability: Beyond NP-Complete Mathematics to allow us to study the scalability of other mathematical methods
Engineering of mathematical methods
Specifications of mathematical methods
Scope of applicability
Scope of practicality
We will consider “Validation Laboratory”
Validate design and approach
Determine weaknesses, specifications
Beyond small scale prototype or simulation
Outside experts, not vendors
Panel 2: Initial Mathematical Topics That Must Be Considered?? : Panel 2: Initial Mathematical Topics That Must Be Considered?? Multi-criteria optimization
The impact of single events, cascades in networks
Methods to accumulate the risks of rare events (also related, statistics of extreme values)
Measuring and controlling emergence
Methods to support different large scale system strategies, e.g. aggregation, abstraction, partitioning… (particularly better methods to map among the levels of multi-resolution systems)
Characterizing solution spaces for quick responses later
Methods to decide whether a sub-graph is characteristic of a much larger graph
Developing mathematics for evaluating partial or intermediate results
Combining results from heterogeneous methods
Mathematical Research Needs in Embedded Systems…in Most DoD Networks : Mathematical Research Needs in Embedded Systems…in Most DoD Networks A real-time embedded system must do the best it can within the time it has,
Designers must be able to reason about the trade-off between the precision of results and the computational time and implement those decision rules in the systems.
Need analytic methods to reason about whether or not more time yields much better answers
Because embedded systems must utilize the currently available data within a set amount of time and hence yield at times intermediate results,
Need advancements in evaluation methods for reasoning about “goodness” of the current solution or the computational progress so far.
In other words, how far off the current result or partial result is from the completed result
Panel 3: Challenge Problems : Panel 3: Challenge Problems Goal of Panel:
Develop challenge problems to help focus national R&D programs
Develop basis for benchmarks to be shared by community for evaluation of computational methods
Composed of Panel 1 and 2 experts.
Outcomes of benefit to OSD:
Hand off challenge problems to DARPA, NSF, other national funding groups to develop programs to address prioritized and critical gaps
Immediately useful to current projects, such as design and evaluation of GIG, and ongoing operations.
Questions to You : Questions to You What does thinking in terms of ‘networks’ buy us in terms of scalability
What are some of the special difficulties in scaling up networks
Back-up : Back-up
Mathematical Research Needs for Dynamic Data Driven Applications Systems (DDDAS) : Mathematical Research Needs for Dynamic Data Driven Applications Systems (DDDAS) “a symbiotic feedback control system [that] entails the ability to dynamically incorporate additional data into an executing application, and in reverse, the ability of an application to dynamically steer the measurement process.”
NSF has identified a number of advances needed in mathematics and statistics in order to handle DDDAS systems.
Many of these topics deal with determining the stability of algorithms and mathematical solutions given the dynamically changing models resulting from the inclusion and incorporation of new data.
NSF’s list includes:“the creation of new mathematical algorithms with stable and robust convergence properties under perturbations induced by dynamic data inputs: algorithmic stability under dynamic data injection/streaming; algorithmic tolerance to data perturbations; multiple scales and model reduction; enhanced asynchronous algorithms with stable convergence properties; stochastic algorithms with provable convergence properties under dynamic data inputs; handling data uncertainty in decision-making/optimization algorithms, especially in cases where decisions can adapt to unfolding scenarios (data paths).”