article

Optimized waveform relaxation methods for longitudinal partitioning of transmission lines

Authors:

Martin J. Gander,

Mohammad Al-Khaleel,

Albert E. RuehliAuthors Info & Claims

IEEE Transactions on Circuits and Systems Part I: Regular Papers, Volume 56, Issue 8

Pages 1732 - 1743

https://doi.org/10.1109/TCSI.2008.2008286

Published: 01 August 2009 Publication History

Abstract

Waveform relaxation (WR) is a technique that can be used to solve large systems of ordinary differential equations (ODEs). It is particularly suitable for the parallel solution of ODEs with multiple time scales and has successfully been used for the solution of electronic circuits and for solving partial differential equations. The main issue limiting the utility of WR is the class of problems with strong subsystem-to-subsystem couplings and long analysis time intervals resulting in nonuniform slow convergence. Here, we consider transmission-line (TL) circuits since they represent an important part of a Spice-type circuit solver. For TLs, the coupling between different lines is relatively weak, and thus, partitioning in the transverse direction leads to very fast WR algorithms. However, longitudinal partitioning of TLs is very challenging due to the strong coupling that results. In this paper, we propose an approach with improved convergence properties for strongly coupled longitudinal partitioning of TLs and other similarly strongly coupled circuits.

References

[1]

Q. Yu, J. M. L. Wang, and E. Kuh, "Passive multipoint moment matching model order reduction algorithm on multiport distributed interconnect networks," IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., vol. 46, no. 1, pp. 140-160, Jan. 1999.

[2]

T. Kim, X. Li, and D. J. Allstot, "Compact model generation for on-chip transmission lines," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 51, no. 3, pp. 459-470, Mar. 2004.

[3]

F. H. Branin, "Transient analysis of lossless transmission lines," Proc. IEEE, vol. 55, no. 11, pp. 2012-2013, Nov. 1967.

[4]

C. Paul, Analyis of Multiconductor Transmission Lines. Hoboken, NJ: Wiley, 1992.

[5]

G. Antonini and G. Ferri, "A new approach for closed-form transient analysis for multiconductor transmission lines," IEEE Trans. Electromagn. Compat., vol. 46, no. 4, pp. 529-543, Nov. 2004.

[6]

E. Gad, C. Chen, and M. Nakhla, "Passivity verification in delay-based macromodels of electrical interconnects," IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 10, pp. 2173-2187, Oct. 2005.

[7]

A. J. Gruodis and F. Y. Chang, "Coupled lossy transmission line characterization and simulation," IBM J. Res. Develop., vol. 25, no. 1, pp. 25-41, Jan. 1981.

Digital Library

[8]

S. Grivet-Talocia, H.-M. Huang, A. Ruehli, F. Canavero, and I. Elfadel, "Transient analysis of lossy transmission line: An efficient approach based on the method of characteristics," IEEE Trans. Adv. Packag., vol. 27, no. 1, pp. 45-56, Feb. 2004.

[9]

N. Nakhla, A. Ruehli, M. Nakhla, R. Achar, and C. Chen, "Waveform relaxation techniques for simulation of coupled interconnects with frequency-dependent parameters," IEEE Trans. Adv. Packag., vol. 30, no. 2, pp. 257-269, May 2007.

[10]

G. Antonini, "A dyadic Green's function based method for the transient analysis of lossy and dispersive multiconductor transmission lines," IEEE Trans. Microw. Theory Tech., vol. 56, no. 4, pp. 880-895, Apr. 2008.

[11]

E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli, "Waveform relaxation decoupling method," IBM Tech. Disclosure Bull., vol. 24, no. 7B, pp. 3720-3720, Dec. 1981.

[12]

E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli, "The waveform relaxation method for time-domain analysis of large-scale integrated circuits," IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. CAD-1, no. 3, pp. 131-145, Jul. 1982.

[13]

F. Y. Chang, "The generalized method of characteristics for waveform relaxation analysis of lossy coupled transmission lines," IEEE Trans. Microw. Theory Tech., vol. 37, no. 12, pp. 2028-2038, Dec. 1989.

[14]

J. K. White and A. Sangiovanni-Vincentelli, Relaxation Techniques for the Simulation of VLSI Circuits. Boston, MA: Kluwer, 1986.

[15]

A. E. Ruehli, Ed., Circuit Analysis, Simulation and Design. North-Holland, The Netherlands: Elsevier, 1987.

[16]

A. E. Ruehli and T. A. Johnson, "Circuit Analysis Computing by Wave-form Relaxation," in Wiley Encyclopedia of Electrical Electronics Engineering. New York: Wiley, 1999, vol. 3.

[17]

J. White and A. L. Sangiovanni-Vincentelli, "Partitioning algorithms and parallel implementations of waveform relaxation algorithms for circuit simulation," in Proc. IEEE ISCAS, Jun. 1985, pp. 1069-1072.

[18]

M. J. Gander and A. Stuart, "Space-time continuous analysis of waveform relaxation for the heat equation," SIAM J. Sci. Comput., vol. 19, no. 6, pp. 2014-2031, Nov. 1998.

Digital Library

[19]

E. Giladi and H. B. Keller, "Space time domain decomposition for parabolic problems," Numer. Math., vol. 93, no. 2, pp. 279-313, 2002.

[20]

M. J. Gander, L. Halpern, and F. Nataf, C. Lai, P. Bjørstad, M. Cross, and O. Widlund, Eds., "Optimal convergence for overlapping and non-overlapping Schwarz waveform relaxation for time dependent problems," in Proc. 11th Int. Conf. Domain Decomposition Methods, Greenwich, U.K., Jul. 20-24, 1998, ddm.org.

[21]

M. J. Gander and L. Halpern, "Méthodes de relaxation d'ndes pour l'équation de la chaleur en dimension 1," C.R. Acad. Sci. Paris, Série I, vol. 336, no. 6, pp. 519-524, 2003.

[22]

M. J. Gander, L. Halpern, and F. Nataf, "Optimal Schwarz waveform relaxation for the one dimensional wave equation," SIAM J. Numer. Anal., vol. 41, no. 5, pp. 1643-1681, 2003.

Digital Library

[23]

M. J. Gander and L. Halpern, "Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems," SIAM J. Numer. Anal., vol. 45, no. 2, pp. 666-697, Feb. 2007.

Digital Library

[24]

V. B. Dmitriev-Zdorov and B. Klaassen, "An improved relaxation approach for mixed system analysis with several simulation tools," in Proc. EURO-DAC, 1995, pp. 274-279, IEEE Comp. Soc. Press.

[25]

V. B. Dmitriev-Zdorov, "Generalized coupling as a way to improve the convergence in relaxation-based solvers," in Proc. EURO-DAC/EURO-VHDL Exhib., Geneva, Switzerland, Sep. 1996.

[26]

M. J. Gander and A. Ruehli, Optimized waveform relaxation methods for RC type circuits IBM Res. Division, New York, Tech. Rep. RC22207, 2001.

[27]

M. J. Gander and A. E. Ruehli, "Solution of large transmission line type problems using a new optimized waveforms relaxation partitioning," in Proc. IEEE Int. Conf. EMC, Boston, MA, Aug. 2003, pp. 636-641.

[28]

M. J. Gander, M. Al-Khaleel, and A. E. Ruehli, "Waveform relaxation technique for longitudinal partitioning of transmission lines," Proc. Dig. Elect. Performance Electron. Packag., pp. 207-210, 2006.

[29]

M. Al-Khaleel, "Optimized waveform relaxation methods for circuit simulations," Ph.D. dissertation, McGill Univ., Montreal, QC, Canada, 2007.

[30]

B. Leimkuhler and A. Ruehli, "Rapid convergence of waveform relaxation," Appl. Numer. Math., vol. 11, no. 1-3, pp. 211-224, Jan. 1993.

Digital Library

Cited By

Gander MKumbhar PRuehli A(2020)Asymptotic Analysis for Overlap in Waveform Relaxation Methods for RC Type CircuitsJournal of Scientific Computing10.1007/s10915-020-01270-584:1Online publication date: 16-Jul-2020
https://dl.acm.org/doi/10.1007/s10915-020-01270-5
Gander MWu S(2019)Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization techniqueNumerische Mathematik10.1007/s00211-019-01060-8143:2(489-527)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s00211-019-01060-8
Antoine XLorin E(2017)An analysis of Schwarz waveform relaxation domain decomposition methods for the imaginary-time linear Schrödinger and Gross-Pitaevskii equationsNumerische Mathematik10.1007/s00211-017-0897-3137:4(923-958)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00211-017-0897-3
Show More Cited By

Recommendations

SOR waveform relaxation methods for stochastic differential equations

Waveform relaxation for solving large-scale systems of ordinary differential equations has extended to stochastic differential equations (SDEs). This paper deals with the acceleration of the Gauss-Sediel waveform relaxation method for SDEs by successive ...
Waveform relaxation methods for fractional differential equations with the Caputo derivatives

In this paper, we report new waveform relaxation methods for fractional differential equations with the Caputo derivatives. The convergence properties of the waveform relaxation methods are studied under linear and nonlinear conditions for the right-...
Optimized Overlapping Schwarz Waveform Relaxation for a Class of Time-Fractional Diffusion Problems

For parabolic PDEs with integer-order temporal derivative, if we use the Schwarz waveform relaxation (SWR) algorithm with Robin transmission conditions as the solver, the so-called equioscillation principle is an important concept to get a good Robin ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Circuits and Systems Part I: Regular Papers

IEEE Transactions on Circuits and Systems Part I: Regular Papers Volume 56, Issue 8

Special section on 2008 custom integrated circuits conference (CICC 2008)

August 2009

351 pages

ISSN:1549-8328

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 August 2009

Revised: 15 August 2008

Received: 27 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gander MKumbhar PRuehli A(2020)Asymptotic Analysis for Overlap in Waveform Relaxation Methods for RC Type CircuitsJournal of Scientific Computing10.1007/s10915-020-01270-584:1Online publication date: 16-Jul-2020
https://dl.acm.org/doi/10.1007/s10915-020-01270-5
Gander MWu S(2019)Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization techniqueNumerische Mathematik10.1007/s00211-019-01060-8143:2(489-527)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s00211-019-01060-8
Antoine XLorin E(2017)An analysis of Schwarz waveform relaxation domain decomposition methods for the imaginary-time linear Schrödinger and Gross-Pitaevskii equationsNumerische Mathematik10.1007/s00211-017-0897-3137:4(923-958)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00211-017-0897-3
Bennequin DGander MGouarin LHalpern L(2016)Optimized Schwarz waveform relaxation for advection reaction diffusion equations in two dimensionsNumerische Mathematik10.1007/s00211-015-0784-8134:3(513-567)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s00211-015-0784-8
Ye ZWu BHan SLi Y(2013)Time-domain segmentation based massively parallel simulation for ADCsProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488905(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488905
Courvoisier YGander M(2013)Optimization of Schwarz waveform relaxation over short time windowsNumerical Algorithms10.1007/s11075-012-9662-y64:2(221-243)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1007/s11075-012-9662-y
Gander MAl-Khaleel MRuehli A(2010)Corrections to optimized waveform relaxation methods for longitudinal partitioning of transmission linesIEEE Transactions on Circuits and Systems Part I: Regular Papers10.1109/TCSI.2010.204199957:1(312-312)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TCSI.2010.2041999

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents