Electronic Circuit Simulation and the Development of New Krylov-Subspace Methods

Ever since the 1960s, the semiconductor industry has heavily relied on simulation in order to analyze and verify the design of integrated circuits before actual chips are manufactured. Over the decades, the algorithms and tools of circuit simulation have evolved in order to keep up with the ever-increasing complexity of integrated circuits, and at certain points of this evolution, new simulation techniques were required. Such a point was reached in the early 1990s, when a new approach was needed to efficiently and accurately simulate the effects of the everincreasing amount of on-chip wiring on the proper functioning of the chip. The industry’s proposed solution for this task, the AWE approach, worked well for smallto moderate-size networks of on-chip wiring, but suffered from numerical issues for larger networks. It turned out that for the special case of networks with single inputs and single outputs, these problems can be remedied by exploiting the connection between AWE and the classical Lanczos algorithm for single starting vectors. However, the general case of on-chip wiring involves networks with multiple inputs and outputs, and so a Lanczos-type algorithm was needed that could handle such multiple starting vectors. Since no such extension existed, a new band Lanczos algorithm for multiple starting vectors was developed. It turned out that this new band approach can also be employed to devise extensions of other Krylov-subspace methods. In this chapter, we describe the band Lanczos algorithm and the band Arnoldi process and how their developments were driven by the need to efficiently and accurately simulate the effects of on-chip wiring of integrated circuits. Roland W. Freund Department of Mathematics, University of California at Davis, One Shields Avenue, Davis, California 95616, USA e-mail: freund@math.ucdavis.edu