Final Report. Analysis and Reduction of Complex Networks Under Uncertainty

Youssef Marzouk, T. Coles, A. Spantini, Luca Tosatto2013 · DOI

TL;DR

This report details a novel approach to simplifying complex, uncertain dynamical systems, particularly those found in chemical kinetics and infrastructure networks. By combining computational singular perturbation (CSP) with probabilistic uncertainty quantification, the researchers developed methods to reduce model complexity while accurately capturing the impact of uncertainties, leading to more tractable and predictive simulations.

What Problem Does This Paper Address?

Many real-world systems, from chemical reactions to power grids, are characterized by complex networks of interacting components with vastly different time scales (multiscale) and inherent uncertainties. Simulating these systems accurately is computationally demanding, often requiring model reduction. Traditional model reduction techniques, like Computational Singular Perturbation (CSP), excel at identifying and simplifying slow dynamics in deterministic systems. However, these methods struggle when faced with uncertainties in parameters or even network structure. This paper tackles the challenge of performing effective model reduction on these complex, uncertain systems, asking how uncertainty transforms the "slow manifolds" that CSP typically identifies and how to build reduced models that account for this.

Methods

The core of the paper's contribution lies in its integration of Computational Singular Perturbation (CSP) with probabilistic uncertainty quantification.

  • CSP: This technique is used to identify and decouple dynamics operating at different time scales, allowing for the approximation of reduced-dimensionality "slow manifolds" where the system's long-term behavior resides.
  • Probabilistic Uncertainty Quantification: To handle uncertainties, the researchers employed stochastic spectral polynomial chaos (PC) methods. This allows them to reformulate uncertain network models into a probabilistic framework.
  • Stochastic CSP: By combining CSP with PC, the analysis is performed in probabilistic terms. This involves solving stochastic eigenvalue problems, often facilitated by projecting onto PC bases, to understand how uncertainty affects the slow manifolds.
  • Rank Reduction: Novel methods for rank reduction in stochastic eigensystems were developed. This aims to transform uncertain dynamical systems into representations with lower storage and solution complexity, making them more computationally manageable.
  • Risk-Based Thresholding: For model simplification in chemical kinetics, a risk-based thresholding approach was introduced. Instead of a deterministic threshold for importance indices, they used the Conditional Value-at-Risk (CVaR). This method is less sensitive to sampling errors and subjective threshold choices, providing a more robust way to decide which reactions to retain in a simplified model, especially under uncertainty.

Datasets

Not discussed in the paper. The paper focuses on developing and evaluating methodologies using established chemical kinetic mechanisms (e.g., methane-air reaction mechanism) and theoretical frameworks for partial differential equations.

Key Insights and Ideas

  • Uncertainty as an Opportunity for Reduction: The paper suggests that uncertainty, rather than just being a nuisance, can sometimes enable greater model reduction. By allowing for larger errors within probabilistic bounds, simplified models can be made smaller.
  • CVaR for Robust Model Reduction: Using CVaR as a threshold for importance indices in CSP provides a more robust way to simplify chemical kinetic models under uncertainty compared to traditional deterministic thresholds. It better captures the risk associated with parameter uncertainties.
  • Topology of Slow Manifolds Under Uncertainty: A key conceptual insight is that parametric uncertainty can fundamentally alter the topology of the slow manifolds that are central to CSP-based reduction. Understanding this transformation is crucial for constructing accurate reduced models.
  • Rank Reduction for Parametric PDEs: The work on rank reduction for parametric PDEs highlights that even if a solution is "high rank" in a naive sense, it might be representable by a low-dimensional map. This suggests that clever transformations (preconditioners) can reveal underlying low-dimensional structure, simplifying computation.

Key Results

  • Improved Chemical Kinetic Model Reduction: The modified CSP simplification algorithm with risk-based thresholding (CVaR) demonstrated improved reproduction of output probability distributions when sampling from a distribution of rate parameters, compared to deterministic CSP. While it didn't always yield lower error for nominal parameters at achievable sizes, it significantly improved the representation of uncertainty.
  • Demonstrated Effectiveness of Stochastic CSP: The paper shows that applying CSP in a probabilistic framework (using PC) can effectively analyze and reduce complex multiscale systems under uncertainty.
  • Novel Rank Reduction Techniques: The development of rank reduction techniques for stochastic eigensystems and parametric PDEs offers a path to significantly reduce storage and solution complexity for uncertain dynamical systems.
  • Comparison with Exhaustive Search: In a deterministic context, CSP-produced simplified mechanisms were found to be within an order of magnitude of optimal error compared to exhaustive search, demonstrating reasonable performance for a heuristic method.

Limitations and Future Work

  • Computational Cost of PC: While PC methods are powerful, their computational cost can still be significant, especially for very high-dimensional systems or complex polynomial expansions. The paper mentions exploring alternatives like Monte Carlo for constructing probability distributions of importance indices, suggesting future work could focus on more efficient stochastic methods.
  • Generality of Simplified Mechanisms: The paper acknowledges that the simplified mechanisms, while optimal for specific error criteria, might not generalize perfectly to all conditions or predict all functionals of species trajectories. Future work could explore broader validation and optimization for multiple criteria.
  • Existence of Low-Rank Preconditioned Fields: For the rank reduction of parametric PDEs, the existence of a low-rank preconditioned field is still an open issue and problem-dependent. Future research will likely focus on conditions under which such fields can be found and how to construct them more reliably.
  • Structural Uncertainties: While the report mentions structural uncertainties (e.g., network links), the primary focus of the presented methods appears to be on parametric uncertainties. Further exploration of methods to handle structural uncertainties in model reduction would be a valuable future direction.

Summary updated

Abstract

The project was a collaborative effort among MIT, Sandia National Laboratories (local PI Dr. Habib Najm), the University of Southern California (local PI Prof. Roger Ghanem), and The Johns Hopkins University (local PI Prof. Omar Knio, now at Duke University). Our focus was the analysis and reduction of large-scale dynamical systems emerging from networks of interacting components. Such networks underlie myriad natural and engineered systems. Examples important to DOE include chemical models of energy conversion processes, and elements of national infrastructure—e.g., electric power grids. Time scales in chemical systems span orders of magnitude, while infrastructure networks feature both local and long-distance connectivity, with associated clusters of time scales. These systems also blend continuous and discrete behavior; examples include saturation phenomena in surface chemistry and catalysis, and switching in electrical networks. Reducing size and stiffness is essential to tractable and predictive simulation of these systems. Computational singular perturbation (CSP) has been effectively used to identify and decouple dynamics at disparate time scales in chemical systems, allowing reduction of model complexity and stiffness. In realistic settings, however, model reduction must contend with uncertainties, which are often greatest in large-scale systems most in need of reduction. Uncertainty is not limited to parameters; one must also address structural uncertainties—e.g., whether a link is present in a network—and the impact of random perturbations, e.g., fluctuating loads or sources. Research under this project developed new methods for the analysis and reduction of complex multiscale networks under uncertainty, by combining computational singular perturbation (CSP) with probabilistic uncertainty quantification. CSP yields asymptotic approximations of reduceddimensionality “slow manifolds” on which a multiscale dynamical system evolves. Introducing uncertainty in this context raised fundamentally new issues, e.g., how is the topology of slow manifolds transformed by parametric uncertainty? How to construct dynamical models on these uncertain manifolds? To address these questions, we used stochastic spectral polynomial chaos (PC) methods to reformulate uncertain network models and analyzed them using CSP in probabilistic terms. Finding uncertain manifolds involved the solution of stochastic eigenvalue problems, facilitated by projection onto PC bases. These problems motivated us to explore the spectral properties stochastic Galerkin systems. We also introduced novel methods for rank-reduction in stochastic eigensystems—transformations of a uncertain dynamical system that lead to lower storage and solution complexity. These technical accomplishments are detailed below. This report focuses on the MIT portion of the joint project.
BibTeX
@misc{marzouk2013final,
  author = {Youssef Marzouk and T. Coles and A. Spantini and Luca Tosatto},
  title = {{Final Report. Analysis and Reduction of Complex Networks Under Uncertainty}},
  year = {2013},
  doi = {10.2172/1224215},
}
Figure