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 xiii

List of Tables xix

Preface xxi

1 Introduction 1

1.1 Device Equations 2

1.2 Equation Formulation 3

1.3 Solution Techniques 6

1.3.1 Nonlinear Circuits 7

1.3.2 Dynamic Circuits 8

1.4 Circuit Simulation Flow 8

1.4.1 Analysis Modes 9

Notes 10

Problems 10

2 Network Equations 13

2.1 Elements and Networks 13

2.1.1 Passive Elements 13

2.1.2 Active Elements 15

2.1.3 Equivalent Circuit Model 17

2.1.4 Network Classification 18

2.2 Topological Constraints 19

2.2.1 Network Graphs 19

2.3 Cycle Space and Bond Space 23

2.3.1 Current Assignments 23

2.3.2 Voltage Assignments 24

2.3.3 Orthogonal Spaces 24

2.3.4 Topological Constraints 25

2.3.5 Fundamental Circulation 25

2.3.6 Fundamental Potential Difference 27

2.4 Formulation of Linear Algebraic Equations 27

2.4.1 Sparse Tableau Analysis 28

2.4.2 Nodal Analysis 29

2.4.3 Unique Solvability 30

2.4.4 Modified Nodal Analysis 33

2.5 Formulation of Linear Dynamic Equations 42

2.5.1 Dynamic Element Stamps 43

2.5.2 Unique Solvability 44

Notes 45

Problems 45

3 Solution of Linear Algebraic Circuit Equations 49

3.1 Direct Methods 50

3.1.1 Matrix Preliminaries 50

3.1.2 Gaussian Elimination (GE) 54

3.1.3 LU Factorization 60

3.1.4 Block Gaussian Elimination 71

3.1.5 Cholesky Decomposition 73

3.2 Accuracy and Stability of GE 74

3.2.1 Error 75

3.2.2 Floating Point Numbers 78

3.2.3 Norms 80

3.2.4 Stability of GE and LU Factorization 83

3.2.5 Pivoting for Accuracy 86

3.2.6 Conditioning of Ax = b 89

3.2.7 Iterative Refinement 96

3.3 Indirect/Iterative Methods 97

3.3.1 Gauss-Jacobi 98

3.3.2 Gauss-Seidel 99

3.3.3 Convergence 100

3.4 Partitioning Techniques 104

3.4.1 Node Tearing 104

3.4.2 Direct Methods 106

3.4.3 Indirect Methods 107

3.5 Sparse Matrix Techniques 109

3.5.1 Sparse Matrix Storage 110

3.5.2 Sparse GE and LU Factorization 112

3.5.3 Reordering and Sparsity 113

3.5.4 Pivoting for Sparsity 115

3.5.5 Markowitz Pivoting 116

3.5.6 Diagonal Pivoting 119

3.5.7 The Symmetric (SPD) Case 120

3.5.8 Extension to the Non-SPD Case 122

Notes 125

Problems 125

4 Solution of Nonlinear Algebraic Circuit Equations 127

4.1 Nonlinear Network Equations 127

4.1.1 Nonlinear Elements 128

4.1.2 Nonlinear MNA Formulation 129

4.1.3 Preparing for a DC Analysis 133

4.2 Solution Techniques 133

4.2.1 Iterative Methods and Convergence 134

4.2.2 Introduction to Newton's Method 136

4.2.3 The One-Dimensional Case 139

4.2.4 The Multidimensional Case 148

4.2.5 Quasi-Newton Methods 152

4.3 Application to Circuit Simulation 154

4.3.1 Linearization and Companion Models 154

4.3.2 Some Test Cases 156

4.3.3 Generalization 162

4.3.4 Considerations for Multiterminal Elements 166

4.3.5 Multivariable Differentiation 167

4.3.6 Linearization of Multiterminal Elements 171

4.3.7 Elements with Internal Nodes 176

4.4 Quasi-Newton Methods in Simulation 181

4.4.1 Damping Methods 182

4.4.2 Overview of More General Methods 186

4.4.3 Source Stepping 187

4.4.4 Gmin Stepping 189

4.4.5 Pseudo-Transient 189

4.4.6 Justification for Pseudo-Transient 193

Notes 196

Problems 197

5 Solution of Differential Circuit Equations 201

5.1 Differential Network Equations 201

5.1.1 Dynamic Elements 201

5.1.2 Dynamic MNA Equations 203

5.1.3 DAEs and ODEs 204

5.2 ODE Solution Techniques 206

5.2.1 ODE Systems and Basic Theorems 206

5.2.2 Overview of Solution Methods 209

5.2.3 Three Basic Methods: FE, BE, and TR 211

5.2.4 Quality Metrics 215

5.2.5 Linear Multistep Methods 220

5.3 Accuracy of LMS Methods 221

5.3.1 Order 221

5.3.2 Consistency 223

5.3.3 The Backward Differentiation Formulas 224

5.3.4 Local Truncation Error 225

5.3.5 Deriving the LMS Methods 228

5.3.6 Solving Implicit Methods 229

5.3.7 Interpolation Polynomial 231

5.3.8 Estimating the LTE 237

5.4 Stability of LMS Methods 241

5.4.1 Linear Stability Theory 242

5.4.2 The Test Equation 243

5.4.3 Absolute Stability 246

5.4.4 Stiff Systems 252

5.4.5 Stiff Stability 253

5.4.6 Remarks 256

5.5 Trapezoidal Ringing 257

5.5.1 Smoothing 258

5.5.2 Extrapolation 259

5.6 Variable Time-Step Methods 261

5.6.1 Implementing a Change of Time-Step 262

5.6.2 Interpolation Methods 262

5.6.3 Variable-Coefficient Methods 264

5.6.4 Variable Step Variable Order (VSVO) Methods 265

5.7 Application to Circuit Simulation 265

5.7.1 From DAEs to Algebraic Equations 266

5.7.2 FE Discretization 269

5.7.3 BE Discretization 271

5.7.4 TR Discretization 277

5.7.5 Charge-Based and Flux-Based Models 282

5.7.6 Multiterminal Elements 291

5.7.7 Time-Step Control 296

5.7.8 Enhancements 298

5.7.9 Overall Flow 299

Notes 300

Problems 300

Glossary 305

Bibliography 307

Index 311