Nyström-Accelerated Primal LS-SVMs: Breaking the $O(n^3)$ Complexity Bottleneck for Scalable ODEs Learning
Weikuo Wang, Yue Liao, Huan Luo
A major problem of kernel-based methods (e.g., least squares support vector machines, LS-SVMs) for solving linear/nonlinear ordinary differential equations (ODEs) is the prohibitive $O(n^3)$ part of their computational complexity with increasing temporal discretization points $n$. We propose a novel Nyström-accelerated LS-SVMs framework that breaks this bottleneck by reformulating ODEs as primal-space constraints. Specifically, we derive for the first time an explicit Nyström-based mapping and its derivatives from one-dimensional temporal discretization points to a higher $m$-dimensional feature space ($1< m\le n$), enabling the learning process to solve linear/nonlinear equation systems with $m$-dependent complexity. Numerical experiments on fifteen benchmark ODEs demonstrate: 1) 10-3000 times faster computation than classical LS-SVMs and physics-informed neural networks (PINNs), 2) comparable accuracy to LS-SVMs ($<0.13$\% relative MAE, RMSE, and $ \| y-\hat{y} \| _{\infty } $difference)  while maximum surpassing PINNs by 72\% in RMSE, and 3) scalability to $n=10^4$ time steps with only $m$=50 features. This work establishes a new paradigm for efficient kernel-based ODEs learning without significantly sacrificing the accuracy of the solution.