Abstract
This paper presents a novel numerical framework for solving convex Fractional Differential Equation (FDE) optimization problems subject to box constraints on state and control variables. By deriving multilevel circulant preconditioners for Krylov subspace methods and embedding them within an Alternating Direction Method of Multipliers (ADMM) framework, we overcome the computational hurdles associated with the dense matrices typical of discretized FDEs. Our approach utilizes recursive linear algebra based on the Fast Fourier Transform (FFT) to maintain linear storage requirements and $O(N \log N)$ computational complexity. Experimental results on time-dependent 2D FDEs demonstrate the scalability and efficiency of the method, successfully solving problems with over two million decision variables on standard hardware.
Introduction
Fractional Differential Equations (FDEs) have emerged as a vital mathematical tool for modeling non-local phenomena, such as anomalous diffusion, turbulent flows, and the memory effects inherent in viscoelastic materials. Unlike standard partial differential equations (PDEs), where local derivatives lead to sparse matrices upon discretization, the non-local nature of fractional derivatives results in dense linear systems.
For a grid with $N$ points, traditional direct solvers require $O(N^3)$ operations and $O(N^2)$ storage. This cubic growth in complexity makes high-resolution modeling (e.g., a $128^3$ grid) practically impossible on standard workstations. Furthermore, practical engineering applications often require "box constraints"—inequality limits on control inputs or allowable states. These constraints typically break the specialized solvers designed for FDEs, forcing a compromise between model accuracy and computational feasibility.
Methodology
To address these challenges, we propose a three-pronged strategy that preserves the underlying structure of the FDE while handling constraints efficiently.
1. The ADMM Framework
We employ the Alternating Direction Method of Multipliers (ADMM) to decouple the complex FDE equality constraints (the physics) from the simple box inequality constraints (the limits). This decomposition allows the algorithm to solve the optimization problem through a sequence of sub-problems, each of which is significantly easier to handle than the original coupled problem.
2. Generalized Locally Toeplitz (GLT) Theory
A critical component of our method is the application of GLT theory. We provide mathematical proof that the structural properties of FDE matrices—specifically their Toeplitz-like nature—are preserved throughout the ADMM iterations. This theoretical foundation is essential, as it justifies the use of specialized preconditioners that rely on matrix structure to accelerate convergence.
3. Multilevel Circulant Preconditioners and FFT
To solve the linear systems arising within the ADMM steps, we utilize the Preconditioned Conjugate Gradient (PCG) method. We approximate the dense FDE matrices with multilevel circulant preconditioners. Because circulant matrices are diagonalized by the Discrete Fourier Transform, matrix-vector multiplications and inversions can be performed in $O(N \log N)$ time using the Fast Fourier Transform (FFT). This reduces the storage requirement to $O(N)$, enabling the handling of massive space-time domains.
Experimental Setup
We evaluated the framework using a series of rigorous test problems on a 3D space-time domain (a 2D spatial square $\Omega$ evolved over time $T$). The target state for the optimization was defined by a complex oscillating function: $$\bar{y}(x_1, x_2, t) = 10 \cos(10x_1) \sin(x_1x_2)(1 - e^{-5t})$$
Experiments were conducted on grids ranging from $8^3$ to $128^3$. The largest configuration involved over 2.09 million decision variables, providing a robust test for the algorithm's scalability.
Key Insights and Results
Structure Preservation
A primary advantage of the ADMM approach over traditional Interior Point Methods (IPMs) is that ADMM does not destroy the Toeplitz structure of the Hessian. This allows our FFT-based solvers to remain efficient until the final iteration, whereas IPMs often lead to increasingly dense and unstructured systems that defeat specialized solvers.
Mesh-Independent Convergence
Our results indicate that the number of iterations required for the inner PCG solver remains nearly constant regardless of the grid refinement. This "mesh-independence" ensures that the computational cost grows predictably with the number of variables, a hallmark of an optimal numerical method.
Performance Benchmarks
On a standard PC, the algorithm demonstrated exceptional speed:
- $N = 50^3$ (125,000 variables): Solved in approximately 74 seconds.
- $N = 128^3$ (2.1 million variables): Solved in roughly 2.5 hours.
As the grid size increased by a factor of 8, the computation time scaled according to the predicted $O(N \log N)$ complexity, rather than the $O(N^3)$ growth expected from standard dense solvers.
Conclusion and Future Work
The proposed framework successfully bridges the gap between high-fidelity fractional modeling and large-scale optimization. While the current method is highly efficient, it is a first-order approach; while it reaches moderate precision quickly, it may require more iterations for extremely high-precision requirements. Additionally, the current implementation assumes constant diffusion coefficients.
Future research will focus on extending these circulant preconditioners to non-constant coefficients using matching Schur complement approximations and exploring higher-order discretization schemes to further enhance accuracy without increasing grid density.
Summary updated