FARID N. NAJM is a Professor in the Department of Electrical and Computer Engineering (ECE) at the University of Toronto. He received a BE degree in electrical engineering from the American University of Beirut (AUB) in 1983 and a PhD degree in ECE from the University of Illinois at Urbana-Champaign (UIUC) in 1989. He then worked with Texas Instruments before joining the ECE Department at UIUC as assistant professor, later becoming associate professor. Dr. Najm joined the ECE Department at the University of Toronto in 1999, where he is currently Professor and Chair. His expertise is in the area of computer-aided design for integrated circuits, with an emphasis on circuit-level issues related to power, timing, variability, and reliability. Dr. Najm is a Fellow of the IEEE.

• List of Figures xiiiList of Tables xixPreface xxi1 Introduction 11.1 Device Equations 21.2 Equation Formulation 31.3 Solution Techniques 61.3.1 Nonlinear Circuits 71.3.2 Dynamic Circuits 81.4 Circuit Simulation Flow 81.4.1 Analysis Modes 9Notes 10Problems 102 Network Equations 132.1 Elements and Networks 132.1.1 Passive Elements 132.1.2 Active Elements 152.1.3 Equivalent Circuit Model 172.1.4 Network Classification 182.2 Topological Constraints 192.2.1 Network Graphs 192.3 Cycle Space and Bond Space 232.3.1 Current Assignments 232.3.2 Voltage Assignments 242.3.3 Orthogonal Spaces 242.3.4 Topological Constraints 252.3.5 Fundamental Circulation 252.3.6 Fundamental Potential Difference 272.4 Formulation of Linear Algebraic Equations 272.4.1 Sparse Tableau Analysis 282.4.2 Nodal Analysis 292.4.3 Unique Solvability 302.4.4 Modified Nodal Analysis 332.5 Formulation of Linear Dynamic Equations 422.5.1 Dynamic Element Stamps 432.5.2 Unique Solvability 44Notes 45Problems 453 Solution of Linear Algebraic Circuit Equations 493.1 Direct Methods 503.1.1 Matrix Preliminaries 503.1.2 Gaussian Elimination (GE) 543.1.3 LU Factorization 603.1.4 Block Gaussian Elimination 713.1.5 Cholesky Decomposition 733.2 Accuracy and Stability of GE 743.2.1 Error 753.2.2 Floating Point Numbers 783.2.3 Norms 803.2.4 Stability of GE and LU Factorization 833.2.5 Pivoting for Accuracy 863.2.6 Conditioning of Ax = b 893.2.7 Iterative Refinement 963.3 Indirect/Iterative Methods 973.3.1 Gauss-Jacobi 983.3.2 Gauss-Seidel 993.3.3 Convergence 1003.4 Partitioning Techniques 1043.4.1 Node Tearing 1043.4.2 Direct Methods 1063.4.3 Indirect Methods 1073.5 Sparse Matrix Techniques 1093.5.1 Sparse Matrix Storage 1103.5.2 Sparse GE and LU Factorization 1123.5.3 Reordering and Sparsity 1133.5.4 Pivoting for Sparsity 1153.5.5 Markowitz Pivoting 1163.5.6 Diagonal Pivoting 1193.5.7 The Symmetric (SPD) Case 1203.5.8 Extension to the Non-SPD Case 122Notes 125Problems 1254 Solution of Nonlinear Algebraic Circuit Equations 1274.1 Nonlinear Network Equations 1274.1.1 Nonlinear Elements 1284.1.2 Nonlinear MNA Formulation 1294.1.3 Preparing for a DC Analysis 1334.2 Solution Techniques 1334.2.1 Iterative Methods and Convergence 1344.2.2 Introduction to Newton’s Method 1364.2.3 The One-Dimensional Case 1394.2.4 The Multidimensional Case 1484.2.5 Quasi-Newton Methods 1524.3 Application to Circuit Simulation 1544.3.1 Linearization and Companion Models 1544.3.2 Some Test Cases 1564.3.3 Generalization 1624.3.4 Considerations for Multiterminal Elements 1664.3.5 Multivariable Differentiation 1674.3.6 Linearization of Multiterminal Elements 1714.3.7 Elements with Internal Nodes 1764.4 Quasi-Newton Methods in Simulation 1814.4.1 Damping Methods 1824.4.2 Overview of More General Methods 1864.4.3 Source Stepping 1874.4.4 Gmin Stepping 1894.4.5 Pseudo-Transient 1894.4.6 Justification for Pseudo-Transient 193Notes 196Problems 1975 Solution of Differential Circuit Equations 2015.1 Differential Network Equations 2015.1.1 Dynamic Elements 2015.1.2 Dynamic MNA Equations 2035.1.3 DAEs and ODEs 2045.2 ODE Solution Techniques 2065.2.1 ODE Systems and Basic Theorems 2065.2.2 Overview of Solution Methods 2095.2.3 Three Basic Methods: FE, BE, and TR 2115.2.4 Quality Metrics 2155.2.5 Linear Multistep Methods 2205.3 Accuracy of LMS Methods 2215.3.1 Order 2215.3.2 Consistency 2235.3.3 The Backward Differentiation Formulas 2245.3.4 Local Truncation Error 2255.3.5 Deriving the LMS Methods 2285.3.6 Solving Implicit Methods 2295.3.7 Interpolation Polynomial 2315.3.8 Estimating the LTE 2375.4 Stability of LMS Methods 2415.4.1 Linear Stability Theory 2425.4.2 The Test Equation 2435.4.3 Absolute Stability 2465.4.4 Stiff Systems 2525.4.5 Stiff Stability 2535.4.6 Remarks 2565.5 Trapezoidal Ringing 2575.5.1 Smoothing 2585.5.2 Extrapolation 2595.6 Variable Time-Step Methods 2615.6.1 Implementing a Change of Time-Step 2625.6.2 Interpolation Methods 2625.6.3 Variable-Coefficient Methods 2645.6.4 Variable Step Variable Order (VSVO) Methods 2655.7 Application to Circuit Simulation 2655.7.1 From DAEs to Algebraic Equations 2665.7.2 FE Discretization 2695.7.3 BE Discretization 2715.7.4 TR Discretization 2775.7.5 Charge-Based and Flux-Based Models 2825.7.6 Multiterminal Elements 2915.7.7 Time-Step Control 2965.7.8 Enhancements 2985.7.9 Overall Flow 299Notes 300Problems 300Glossary 305Bibliography 307Index 311