Optimized waveform relaxation methods for circuit simulations

Waveform Relaxation methods are very efficient and reliable methods. They have been widely used in several fields, including circuit theory, for solving large systems of ordinary differential equations and solving partial differential equations. A new approach called optimized waveform relaxation algorithms was recently introduced which greatly improved convergence by using new transmission conditions. These conditions are responsible for the exchange of information between subsystems. In this thesis, we demonstrate that the transmission conditions have a tremendous influence on the convergence of the waveform relaxation algorithms for circuit simulations. We first derive new waveform relaxation methods for a general circuit and its associated system of ordinary differential equations, and give transmission conditions with optimal performance. These optimal transmission conditions are however not convenient to use and thus we introduce approximations for them. We then determine numerically the approximate transmission conditions with the best performance of the new waveform relaxation algorithms for two model problems, and we show how much the convergence can be improved compared to the classical waveform relaxation algorithm. We then start a detailed study of optimized waveform relaxation algorithms for RC type circuits. We first analyze RC circuits of any finite size, and give optimal transmission conditions. We again propose approximations for the optimal transmission conditions which are optimized based on numerical insight. Then we choose a very small RC circuit which has only one cell and a small RC circuit which has three cells to further study the quality of the approximations. For the very small RC circuit we show that the optimal transmission conditions are indeed local operators in time, they are first degree time derivatives which are convenient to use. However; we also propose a constant approximation of the optimal transmission conditions which is simpler to use and we prove the optimality of this approximation. For the small RC circuit we also prove the optimality of the proposed constant approximation, and find asymptotically an optimized first order approximation. We then study an infinitely large RC circuit to demonstrate that the size of the circuit does not have a major impact on the convergence of the optimized waveform relaxation methods. We recall the optimality proof for the constant approximation given in [1], and we give an asymptotic result for an optimized first order approximation. We show that results found for the infinitely large RC circuit are indeed limits of those found for the finite size RC circuit as the size of the circuit goes to infinity. We next start a detailed study of optimized waveform relaxation algorithms for transmission line type circuits. We give optimal transmission conditions which we approximate by constants. We analyze very small and small transmission line circuits, which have one cell and two cells respectively, and we find asymptotically optimized constant transmission conditions for both. We consider also an infinitely large transmission line circuit, and we give an optimized constant approximation based on an asymptotic analysis. We finally show that the systems representing the circuits considered are semi-discretizations of particular partial differential equations, and in addition, we show that the new transmission conditions introduced for the circuit problems imply the ones associated with the partial differential equations at the continuous level. We also show that the convergence factors and the solutions obtained by applying the new waveform relaxation algorithms to the partial differential equations converge to those obtained by applying the algorithms to the circuit systems. In order to demonstrate the practicality and the efficiency of the optimized waveform relaxation methods; we give numerical experiments that show the drastically improved convergence beh...