Computational Complexity Analysis of Interval Methods in Solving Uncertain Nonlinear Systems

View PDF HTML (experimental)

Abstract: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.

Comments: 20 pages, 2 figures

Subjects:

Data Structures and Algorithms (cs.DS); Systems and Control (eess.SY)

Cite as: arXiv:2603.19965 [cs.DS]

(or arXiv:2603.19965v2 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2603.19965

arXiv-issued DOI via DataCite

Submission history

From: Rudra Prakash [view email] [v1] Fri, 20 Mar 2026 14:06:03 UTC (162 KB) [v2] Tue, 31 Mar 2026 07:16:57 UTC (162 KB)