Efficient approximation of symbolic network functions using matroid intersection algorithms

Abstract

An efficient and effective approximation strategy is the key to the symbolic analysis of large analog circuits. In this paper we propose a new approximation strategy, which directly generates common spanning trees of a two-graph in decreasing order of tree admittance product using matroid intersection algorithms. Our strategy reduces the total time for computing an approximate symbolic expression in expanded format to polynomial with respect to the circuit size and the number of sample frequencies in the range of interest, assuming the number of product terms retained in the final expression is polynomial.