Fixed-precision randomized low-rank approximation methods for nonlinear model order reduction of large systems

Many model order reduction (MOR) methods employ a reduced basis V is an element of Rmxk to approximate the state variables. For nonlinear models, V is often computed using the snapshot method. The associated low-rank approximation of the snapshot matrix A is an element of Rmxn can become very costly as m,n grow larger. Widely used conventional singular value decomposition methods have an asymptotic time complexity of O(min(mn2,m2n)), which often makes them impractical for the reduction of large models with many snapshots. Different methods have been suggested to mitigate this problem, including iterative and incremental approaches. More recently, the use of fast and accurate randomized methods was proposed. However, most work so far has focused on fixed-rank approximations, where rank k is assumed to be known a priori. In case of nonlinear MOR, stating a bound on the precision is usually more appropriate. We extend existing research on randomized fixed-precision algorithms and propose a new heuristic for accelerating reduced basis computation by predicting the rank. Theoretical analysis and numerical results show a good performance of the new algorithms, which can be used for computing a reduced basis from large snapshot matrices, up to a given precision epsilon.