Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!pasteur!ucbvax!hplabs!analog2!wayne!kim
From: kim@wayne.UUCP (Kim Helliwell)
Newsgroups: comp.lsi.cad
Subject: Re: Spice runtime vs # of transistors
Summary: why is O(n^1.35) behavior a surprise?
Message-ID: <236@wayne.UUCP>
Date: 29 Aug 88 23:07:38 GMT
References: <2913@obiwan.mips.COM>
Organization: Analog Design Tools Inc., Sunnyvale, CA.
Lines: 44

In article <2913@obiwan.mips.COM>, mark@mips.COM (Mark G. Johnson) writes:
> 
> Summary:    An unusual and perhaps surprising result was found, running
>         SPICE on a parameterized MOS circiut.  The measured runtimes
> 	show an asymptotic complexity (in the sense of "big-O" asymptotes)
> 	of n ^ 1.35  where n is the number of MOSFETs.
>             What may appear unusual is that the super-linear term is
> 	dominated by the linear	term for n < 43,000 transistors.   {This
>         is an extrapolation; the experimental data only extends to
> 	n=1000 transistors}

Followed by some data and a derivation of a fitted curve.  He seemed
surprised by this behavior, but it matches very well what I know about
SPICE, and what Berkeley people (e.g. Prof Newton) say about it.

Basically, the linear term comes from the equation formulation--the 
model calculation and matrix loading.  It should seem intuitive that this
part of things is linear in the number of transistors.

The superlinear term comes from the matrix solution.  I agree that it may
not be intuitive that this term is dominated by the linear term, but 
Newton and many others have known that for years.

Normally, you expect that matrix solution would be O(n^3), so why is that
not the case here?  Simply because of the efficiencies introduced by
maintaining a sparse matrix--because so many of the elements are identically
zero, many of the steps of doing the matrix solution can be skipped entirely.
This results in asymptotic behavior that goes like O(n^1.1-1.4), according
to Newton.  In fact, in the limiting case of NO off-diagonal elements in the
matrix, it would be O(n)!

By the way, this is why so much emphasis is put on maintaining sparsity
throughout the solution process, and why pivots are chosen more based on
preserving sparsity than on preserving accuracy.  (If you don't know
what that means, you can either ignore it or read Nagel's thesis--the
chapter where he talks about matrix solution techniques.)



-- 

"Never let work interfere with your reasons for working."

Kim Helliwell