Computational Complexity Analysis of Interval Methods in Solving Uncertain Nonlinear Systems
It addresses computational bottlenecks in validated uncertainty analysis for applications like biochemical modeling, though it is incremental in refining existing methods.
This paper analyzes the computational complexity of interval methods for solving uncertain nonlinear systems, deriving worst-case time and space bounds for algorithms like interval bisection and interval Newton, and shows that naive interval matrix operations scale factorially with dimension.
This paper analyses the computational complexity of validated interval methods for uncertain nonlinear systems. Interval analysis produces guaranteed enclosures that account for uncertainty and round-off, but its adoption is often limited by computational cost in high dimensions. We develop an algorithm-level worst-case framework that makes the dependence on the initial search volume $\mathrm{Vol}(X_0)$, the target tolerance $\varepsilon$, and the costs of validated primitives explicit (inclusion-function evaluation, Jacobian evaluation, and interval linear algebra). Within this framework, we derive worst-case time and space bounds for interval bisection, subdivision$+$filter, interval constraint propagation, interval Newton, and interval Krawczyk. The bounds quantify the scaling with $\mathrm{Vol}(X_0)$ and $\varepsilon$ for validated steady-state enclosure and highlight dominant cost drivers. We also show that determinant and inverse computation for interval matrices via naive Laplace expansion is factorial in the matrix dimension, motivating specialised interval linear algebra. Finally, interval Newton and interval Krawczyk have comparable leading-order costs; Krawczyk is typically cheaper in practice because it inverts a real midpoint matrix rather than an interval matrix. These results support the practical design of solvers for validated steady-state analysis in applications such as biochemical reaction network modelling, robust parameter estimation, and other uncertainty-aware computations in systems and synthetic biology.