Multipoint Padé approximation using a rational block Lanczos algorithm

ABSTRACT

This paper presents a general rational block Lanczos algorithm for computing multipoint matrix Pade approximation of linear multiport networks, which model many important circuits in digital, analog, or mixed signal designs. This algorithm generalizes a novel block Lanczos algorithm with a reliable adaptive scheme for breakdown treatment to address two drawbacks of the single frequency Pade approximation: poor approximation of the transfer function in the frequency domain far away from the expansion point and the instability of the reduced model when the original system is stable. In addition, due to smaller Krylov subspace corresponding to each frequency point, the rational algorithm also alleviates the possible breakdowns when completing high order approximations. The cost of full backward orthogonalization with respect to all previous Lanczos vectors in a rational Lanczos algorithm, as compared to a partial backward orthogonalization in a single point Lanczos algorithm, is offset by more accurate and smaller order approximations.

REFERENCES

• 1: A. Bai , D. Day , J. D %A , J. Dongarra, A Test Matrix Collection for Non-Hermitian Eigenvalue Problems, University of Tennessee, Knoxville, TN, 1997
• 2: K. Gallivan, E. Grimme, and E Van Dooren, "Pad6 Approximation of Large-Scale Dynamic Systems with Lanczos Methods", Proc. IEEE Conf. on Decision and Control, vol.1, pp. 443-448, 1994.
• 3: L.T. Pillage and R. A. Rohrer, "Asymptotic Waveform Evaluation for Timing Analysis," IEEE Trans. Computer-Aided Design, vol. 9, pp. 352- 366, Apr. 1990.
• 4: E Feldmann and R. W. Freund, "Efficient Linear Circuit Analysis by Pad6 Approximation via the Lanczos Process," IEEE Trans. Computer- Aided Design, vol. 14, pp. 639-649, May 1995.
• 5: K. Gallivan, E. Grimme, and E Van Dooren, "Asymptotic Waveform Evaluation via a Lanczos Method," Appl. Math. Lett., vol. 7, No. 5, pp.75- 80, 1994.
• 6: P. Feldmann , R. W. Freund, Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.474-479, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217573]
• 7: T.V. Nguyen, J. Li, and Z. Bai, "Dispersive Coupled Transmission Line Simulation Using an Adaptive Block Lanczos Algorithm," Proc. CICC, pp. 457-460, May 1996.
• 8: T.V. Nguyen and J. Li, "A Rational Adaptive Block Lanczos Algorithm for Reduced Order Modeling of Linear(ized) Circuits," Motorola Technical Report.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
Krylov subspace, Lanczos vectors, analog design, circuit simulation, digital design, expansion point, frequency domain, full backward orthogonalization, linear multiport networks, mixed signal design, multipoint matrix Pade approximation, multiport networks, rational block Lanczos algorithm, reduced model, reliable adaptive scheme, single frequency Pade approximation, transfer function