Compressed block-decomposition algorithm for fast capacitance extraction

Alex Heldring; Juan M. Rius; José Maria Tamayo; Josep Parrón

doi:https://doi.org/10.1109/TCAD.2007.907236

Compressed block-decomposition algorithm for fast capacitance extraction

Alex Heldring, Juan M. Rius, José Maria Tamayo, Josep Parrón

Research output: Contribution to journal › Article › Research › peer-review

21 Citations (Scopus)

Abstract

A novel algorithm, the compressed block decomposition, is presented for highly accelerated direct (noniterative) method-of-moment capacitance extraction. The algorithm is based on a blockwise subdivision of the method-of-moment potential coefficient matrix. Matrix subblocks corresponding to distant subregions of the problem geometry are not calculated directly but approximated in a compressed form. Subsequently, the matrix is decomposed using an algorithm that preserves the compression. The efficiency of the method is demonstrated on a common benchmark problem - a 6 × 6 bus crossing. The numerical cost of the algorithm is shown, both theoretically and numerically, to scale with N log3 N and the storage space with N log2 N. © 2008 IEEE.

Original language	English
Pages (from-to)	265-271
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	27
DOIs	https://doi.org/10.1109/TCAD.2007.907236
Publication status	Published - 1 Feb 2008

Keywords

Capacitance extraction
Fast direct solvers
Method of moments

Access to Document

https://doi.org/10.1109/TCAD.2007.907236

Cite this

@article{e011784996d74e4c9b2d726f6b7bcd75,

title = "Compressed block-decomposition algorithm for fast capacitance extraction",

abstract = "A novel algorithm, the compressed block decomposition, is presented for highly accelerated direct (noniterative) method-of-moment capacitance extraction. The algorithm is based on a blockwise subdivision of the method-of-moment potential coefficient matrix. Matrix subblocks corresponding to distant subregions of the problem geometry are not calculated directly but approximated in a compressed form. Subsequently, the matrix is decomposed using an algorithm that preserves the compression. The efficiency of the method is demonstrated on a common benchmark problem - a 6 × 6 bus crossing. The numerical cost of the algorithm is shown, both theoretically and numerically, to scale with N log3 N and the storage space with N log2 N. {\textcopyright} 2008 IEEE.",

keywords = "Capacitance extraction, Fast direct solvers, Method of moments",

author = "Alex Heldring and Rius, {Juan M.} and Tamayo, {Jos{\'e} Maria} and Josep Parr{\'o}n",

year = "2008",

month = feb,

day = "1",

doi = "https://doi.org/10.1109/TCAD.2007.907236",

language = "English",

volume = "27",

pages = "265--271",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Compressed block-decomposition algorithm for fast capacitance extraction

AU - Heldring, Alex

AU - Rius, Juan M.

AU - Tamayo, José Maria

AU - Parrón, Josep

PY - 2008/2/1

Y1 - 2008/2/1

N2 - A novel algorithm, the compressed block decomposition, is presented for highly accelerated direct (noniterative) method-of-moment capacitance extraction. The algorithm is based on a blockwise subdivision of the method-of-moment potential coefficient matrix. Matrix subblocks corresponding to distant subregions of the problem geometry are not calculated directly but approximated in a compressed form. Subsequently, the matrix is decomposed using an algorithm that preserves the compression. The efficiency of the method is demonstrated on a common benchmark problem - a 6 × 6 bus crossing. The numerical cost of the algorithm is shown, both theoretically and numerically, to scale with N log3 N and the storage space with N log2 N. © 2008 IEEE.

AB - A novel algorithm, the compressed block decomposition, is presented for highly accelerated direct (noniterative) method-of-moment capacitance extraction. The algorithm is based on a blockwise subdivision of the method-of-moment potential coefficient matrix. Matrix subblocks corresponding to distant subregions of the problem geometry are not calculated directly but approximated in a compressed form. Subsequently, the matrix is decomposed using an algorithm that preserves the compression. The efficiency of the method is demonstrated on a common benchmark problem - a 6 × 6 bus crossing. The numerical cost of the algorithm is shown, both theoretically and numerically, to scale with N log3 N and the storage space with N log2 N. © 2008 IEEE.

KW - Capacitance extraction

KW - Fast direct solvers

KW - Method of moments

U2 - https://doi.org/10.1109/TCAD.2007.907236

DO - https://doi.org/10.1109/TCAD.2007.907236

M3 - Article

VL - 27

SP - 265

EP - 271

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

ER -

Compressed block-decomposition algorithm for fast capacitance extraction

Abstract

Keywords

Access to Document

Fingerprint

Cite this