Towards a Parallel-in-Time Calculation of Time-Periodic Solutions with Unknown Period

This paper presents a novel parallel-in-time algorithm able to compute time-periodic solutions of problems where the period is not given. Exploiting the idea of the multiple shooting method, the proposed approach calculates the initial values at each subinterval as well as the corresponding period iteratively. As in the Parareal method, parallelization in the time domain is performed using discretization on a two-level grid. A special linearization of the time-periodic system on the coarse grid is introduced to speed up the computations. The iterative algorithm is verified via its application to the Colpitt oscillator model.


Introduction
Steady-state analysis is a common task in electrical engineering, for example, during the initial design stages of, e.g., electric circuits or motors. Classical sequential time stepping may lead to lengthy transient computation particularly when the underlying dynamical system possesses a large time constant. Various approaches for efficient steady-state calculation are known from the literature. For instance, clever methods to choose the starting value [1] or an explicit error correction [14] could accelerate the time-domain calculation considerably.
A powerful tool for speeding up the classical time stepping is the class of parallelin-time methods, such as the multigrid reduction in time [5] or Parareal [11]. Originating from the multiple shooting method [12], they are based on the splitting of the considered time interval into several windows and updating the solution at synchronization points iteratively. The use of coarse and fine discretizations propagates quickly low-frequency information of the solution using a cheap sequential solver followed by a very accurate result with a precise fine solver applied in parallel. Another direction of obtaining the steady state is based on the solution of the joint space-and time-discrete time-periodic system formulated on the whole period [8]. There the initial and final values are coupled through the prescribed periodicity condition. An obstacle within the solution of the periodic problem in the time domain becomes the large size of the system matrix as well as its special block structure due to the interdependence of the solution vectors over the period. To deal with this difficulty a frequency domain approach was proposed in [2]. In case of linear problems, the method takes advantage of the block-cyclic matrix structure by applying the discrete Fourier transform. It fully decouples the variables, thereby allowing for the separate solution of each harmonic coefficient. This approach was further extended and incorporated into the Parareal framework by the authors in [10]. There, a simplified Newton-based iterative algorithm was presented together with its convergence analysis for the efficient treatment of nonlinear problems.
Solutions of time-periodic problems become much more challenging when the period is not given. Such situation occurs, e.g., when dealing with an atonomous system [4]. In contrast to a non-atonomous problem, the periodicity cannot be determined from the applied excitation. This paper proposes a numerical algorithm capable of determining an appropriate period automatically using parallelization in the time domain. Extending the idea of the multiple shooting method we include the unknown period together with multiple initial values as the sought parameters into the iterative procedure. Verification of the presented approach is illustrated through its application to the Colpitt oscillator model [9].
The paper is organized as follows. Section 2 describes the basis of the multiple shooting approach including the unknown period as an additional variable. This is further expanded to the family of the Parareal-based methods in Section 3. Section 4 applies the proposed parallel-in-time approach to the Colpitt oscillator model using a particular linerization on the coarse level. The paper is finally summarized in Section 5.

Multiple shooting with unknown period
We consider the following time-periodic problem for a system of ordinary differential equations (ODEs) where the period T > 0 and the vectorũ : M is a given (regular) mass matrix, f is a bounded and Lipschitz continous right-hand-side (RHS) function. Following [3] we incorporate the period T as an unknown parameter by performing the change of variables Fig. 1 Example of the interval splitting within the multiple shooting for N = 5. The mismatches at the synchronization points τ n , n = 1, . . ., N − 1 together with the periodicity jump between the solution at τ 0 and τ N are eliminated (up to a prescribed tolerance) by solving the root-finding problem.
A sketch of the piecewise-defined solution due to the interval splitting is shown in Fig. 1. In order to eliminate the jumps at the synchronization points τ n , n = 1, . . . , N − 1 as well as the difference between the initial value at τ 0 and the final one at τ N the matching conditions: (5) represents the rootfinding problem for the mapping Φ : R Nd+1 → R Nd . The Jacobian of Φ is given by where n = 1, . . . , N and I is the identity matrix. The root z of (5) can then be calculated using the Newton method, i.e., for a given z (0) and k = 0, 1, . . . solution z (k+1) at the iteration k + 1 is updated through Note that due to the introduction of the additional variable T the system of equations (8) is underdetermined and can be solved, e.g., by calculating the Moore-Penrose pseudoinverse. Besides, in case when the size of (8) is large it can be condensed to a d-dimensional system with d + 1 unknowns by block Gaussian elimination [3,4].

Periodic time-parallelization with coarse grid correction
Inheriting the idea of the Parareal algorithm [7,11] we approximate the derivative in G n (7) in a finite difference way using a coarse propagator G , i.e., for the iteration k and n = 1, . . . , N Similar to the fine propagator F , the operator G solves the IVP (4) on each time window. However, in contrast to the fine solver the coarse propagator has a considerably lower precision, e.g., it uses a lower-order time integrator or bigger time steps. Substituting (10) into (8) we obtain the periodic Parareal with periodic coarse problem [6] with unknown period (PP-PC-UP): n−1 and following [3] for n = 1, . . . , N. In the general case, the system of equation (11) is nonlinear and implicit, which requires an additional linearization. Building upon the ideas presented in [10], which dealt with the time-periodic problem for a known given period T , we encorporate an additive splitting of the system matrix in (11). For this let us introduce a modified coarse propagatorḠ , which instead of (4) solves an approximate model with a linearized functionf(u) = Au + c on the RHS, i.e., with a given Jacobi-matrix A n and a vector c. Having the linear coarse model we construct a fixed point iteration: for s = 0, 1, . . . for n = 1, . . . , N. Assuming thatḠ solves (13) with the implicit Euler method using a single step on (τ n−1 , τ n ] and that all the windows have the same length ∆ τ, we have an explicit representation for the coarse solution for n = 1, . . . , N. Denoting by C := 1/∆ τ · M and Q (k) := C − T (k) A and plugging this into the system (13) we obtain Remark 1 We note that when the period T is given within the problem setting (1), the corresponding block-cyclic matrix (system matrix of (3) without the last column) can be transformed into a block-diagonal using the frequency domain transformation [2]. A detailed description of the approach as well as a Newton-like linearization of the periodic system within the parallel-in-time setting is presented in [10].

Numerical example
We now consider the Colpitt oscillator model presented in [9]. It is described by the circuit illustrated in Fig. 2, which consists of an inductance, a bipolar transistor, as well as of four capacitances and four resistances. The Colpitt oscillator model was exploited in the multi-rate context in [13]. The mathematical model of the circuit is given by an implicit system of ODEs [9], namely, we search for the four node voltages U = [U 1 ,U 2 ,U 3 ,U 4 ] ⊤ s.t. To find the periodic steady-state solution and the corresponding period T we apply the iteration (14). Linearization of the nonlinear periodic system on the coarse level is performed using a surrogate linear model, i.e.,Ḡ solves the problem (13) withf(U) = AU + c given by withŪ T = 0.2585V. The unit interval [0, 1] is split into N = 10 windows. The coarse time step ∆ τ = 0.1 and the fine step δ τ = 10 −4 were chosen within the time integration. The calculated period with the fixed point iteration (3) is T = 0.1125ms. The right-hand part of the Fig. 3 shows convergence of the PP-PC iteration with the linearization from [10] for a given period T as well as for an unknown period (PP-PC-UP). Both results are obtained up to the relative tolerance of 10 −3 . One can see that in case when T is known the method required less iterations, as one would expect. When comparing the computational cost of the computations in terms of the number of linear systems solves, PP-PC and PP-PC-UP delivered the periodic solution effectively 4 and 3 times faster than the sequential time stepping, respectively.

Conclusions
An iterative parallel-in-time method for solving time-periodic problems where the period is not initially given is proposed in this paper. It complements the system of equations originating from the Parareal-like algorithm with an additional variable T and gives an underdetermined system of nonlinear equations. A linearization using the fixed point iteration is applied on the coarse grid. The algorithm is verified through its application to a Colpitt oscillator model.