<html>
https://i.postimg.cc/qqVXH41R/circuit-sim-series.jpg<br>
[Custom Thumbnail]<br>
All the Code of the series can be found at the <strong>Github repository</strong>:
https://github.com/drifter1/circuitsim
<hr>
<h1>Introduction</h1> Hello it's a me again @drifter1! Today we continue with the <strong>Electronic Circuit Simulation series</strong>, a tutorial series where we will be implementing a full-on electronic circuit simulator (like SPICE) studying the whole concept and mainly physics behind it! Following the theoretical approach of the previous part, we will today <strong>implement the CSR and CSC formats of Sparse Matrices in Python</strong>, by also using CSC to <strong>optimize our Static Analysis Simulator</strong>...
<h2>Requirements:</h2>
<ul>
<li>Physics and more specifically <strong>Electromagnetism Knowledge</strong></li>
<li>Knowing <strong>how to solve Linear Systems</strong> using Linear Algebra</li>
<li>Some understanding of the <strong>Programming Language Python</strong></li>
</ul>
<h2>Difficulty:</h2>Talking about the <strong>series in general</strong> this series can be rated:
<ul><li>Intermediate to Advanced</li></ul>
<strong>Today's topic(s)</strong> can be rated:
<ul><li>Intermediate</li></ul>
<hr>
<h1>Actual Tutorial Content</h1>
<h2>Sparse Matrices using SciPy</h2> As we described in the previous article, Sparse Matrices are very important as they will make storing the A-matrix more memory efficient. The incremental construction of the matrix is done using either one of the formats: DOK, LIL or COO. Because we want to use the matrix later on in calculations, meaning that we want to convert the sparse matrix into CSR or CSC format, we will use COO, as this format allows a fast conversion to CSR or CSC. So, let's get started!
<h3>Create Sparse Matrix - COO Format</h3> First of all, to use all these different structures and functions that are provided by the SciPy library we have to <strong>import the package</strong> using:<br>
<pre><code>import scipy.sparse as sparse</code></pre><br>
What exactly is COO again? COO is a Coordinate List that basically <strong>stores a list of (row, column, value) tuples or triplets</strong>. To create such a matrix in Python we have to feed in 3 arrays/lists:<br>
<ol>
<li>The rows of all non-zero values</li>
<li>The columns of all non-zero values</li>
<li>The actual non-zero values</li>
</ol><br>
So, a general <strong>coo_matrix</strong> is defined as:<br>
<pre><code>A = sparse.coo_matrix((data, (rows, cols)), shape=(dim, dim))</code></pre><br>
To create these three lists or arrays more efficiently and with less need of Code, we can create a structure that keeps those three arrays/lists and appends values to them. Let's call this structure <strong>Triplet</strong>. Whenever we want to insert an entry, we will basically add the row, column and value (or data) to the corresponding lists rows, cols and data. Such a class looks like this:<br>
<pre><code>class Triplet:
def __init__(self):
self.rows = []
self.cols = []
self.data = []<br>
def insert(self, row, col, data):
self.rows.append(row)
self.cols.append(col)
self.data.append(data)<br>
def __repr__(self):
return "rows: " + str(self.rows) + "\ncols: " + str(self.cols)
+ "\ndata: " + str(self.data)</code></pre><br>
Let's recall our <strong>classic example circuit</strong> that gives us the system:<br>
https://steemitimages.com/640x0/https://quicklatex.com/cache3/f6/ql_2a03bbd062a53d2b4ae667bf91d417f6_l3.png<br><br>
Thinking about the creation procedure, <strong>the [1, 1] entry is basically a sum between 0.25 and 0.5</strong>, which are caused by each of the two resistances. So, during the creation <strong>we will have duplicate entries for such cases</strong>! That's also a very important reason to why we are using COO in the first place, cause the other matrices don't store the duplicates and just keep the last occurrence. In other cases, this might be helpful, but for us it is not at all! After converting the COO matrix to CSR or CSC, the duplicates are summed up together, giving us exactly what we want...<br><br>
So, let's <strong>fill in the triplets lists</strong>:<br>
<pre><code>triplets = Triplet()<br>
# add impact of R1
triplets.insert(0, 0, 0.25)
triplets.insert(0, 1, -0.25)
triplets.insert(1, 0, -0.25)
triplets.insert(1, 1, 0.25)<br>
# add impact of R2
triplets.insert(1, 1, 0.5)<br>
# add impact of V1
triplets.insert(0, 2, 1)
triplets.insert(2, 0, 1)<br>
print(triplets, "\n")</code></pre><br>
This last print gives us:<br>
https://i.postimg.cc/3rXdhNHg/image.png<br><br>
We can clearly see that there are two entries for [1, 1], as we expected!<br><br>
Last but not least let's also <strong>setup the actual matrix</strong>:<br>
<pre><code>mtx = sparse.coo_matrix(
(triplets.data, (triplets.rows, triplets.cols)), shape=(3, 3))</code></pre><br>
It will also be wise to delete the triplets using:<br>
<pre><code>del triplets</code></pre>
<h3>Convert to more efficient Format (CSR/CSC)</h3> Converting the COO format to CSR or CSC can be done veeeery easily using only one function call:<br>
<ul>
<li>tocsr() - convert to CSR format</li>
<li>tocsc() - convert to CSC format</li>
</ul>
<br>
Doing each of these and printing out the format we have...<br>
https://i.postimg.cc/tTHD1Jvh/image.png<br><br>
https://i.postimg.cc/PrqyvByF/image.png<br><br>
Can you guess, which one is CSR and which CSC? That's quite easy I think! We don't sort the entries, and so the "convertion" procedure left behind a very important mark. If you remember from last time, we loop through the matrix in either row-major order, which gives us CSR or column-major order, which gives us CSC. So, seeing that the first loops through each row and the second through each column first, we can understand that the first is CSR, whilst the second is CSC, even without knowing which function was used!<br><br>
In code those two conversions are:<br>
<pre><code># convert to CSR
A = mtx.tocsr()<br>
# convert to CSC
A = mtx.tocsc()
</code></pre><br>
To <strong>print out the dense matrix</strong> we can use "todense()", which for both cases gives us:<br>
https://i.postimg.cc/qqvFRgg1/image.png
<h3>Solving Linear System</h3>We first have to define the numpy array of b:<br>
<pre><code>b = np.array([0, 2, 3])</code></pre><br>
Solving the system is basically again just calling a function from a specific part of scipy.sparse that has to do with linear algebra solving. For now, we will use a direct solve approach that of course has to take in a sparse matrix (A) and dense matrix (b). More specifically this function can be imported from:<br>
<pre><code>from scipy.sparse.linalg.dsolve import linsolve</code></pre><br>
Using this function to solve our system looks like this:<br>
<pre><code>x = linsolve.spsolve(A, b)</code></pre><br>
Printing out the solution x we get:<br>
https://i.postimg.cc/4dsfWvFn/image.png<br><br>
which are the same results that we got without sparse matrices!<br><br>
On GitHub I include the whole code for CSR and CSC...
<hr>
<h2>Optimizing the Static Analysis Simulator</h2> To optimize our current simulator, we basically only have to define the same Triplet class and insert the corresponding (row, column, value) pairs into the triplets lists. So, we will no longer have a numpy array for A, but will setup an instance of the Triplet class using:<br>
<pre><code>triplets = Triplet()</code></pre><br>
While looping through the components and adding entries to the A-matrix, we will actually have to use the "insert()" function of Triplet. For example for voltage sources we now have:<br>
<pre><code>elif component.comp_type == 'V':
# affects the B and C matrices of A
if high != 0:
triplets.insert(high-1, g2Index, 1)
triplets.insert(g2Index, high-1, 1)
if low != 0:
triplets.insert(low-1, g2Index, -1)
triplets.insert(g2Index, low-1, -1)<br>
# affects b-matrix
b[g2Index] = value<br>
# increase G2 counter
g2Index = g2Index + 1
</code></pre><br>
After the loop, we will use the triplet lists: data, rows and cols, to setup the actual sparse matrix in COO format, by then converting it to CSC format:<br>
<pre><code># setup sparse matrix A
mtx = sparse.coo_matrix(
(triplets.data, (triplets.rows, triplets.cols)), shape=(matrixSize, matrixSize))<br>
del triplets<br>
# convert to CSC
A = mtx.tocsc()</code></pre><br>
The solving function of course has to be replaced with the new "sparse" one:<br>
<pre><code>def solveSystem(A, b):
x = linsolve.spsolve(A, b)
return x</code></pre><br>
Running our Simulator for the simple example we get:<br>
https://i.postimg.cc/T2qKr11t/image.png<br><br>
And so nothing really changed!<br><br>
Running it for some of the other examples we would also see no different in the result values. So, what was this all for? As we also explained last time, Sparse matrices are of no use in such small Netlists, but will be essential for us when solving larger Netlists! Let's try to run the first Netlist from the following website:<br>
http://tiger.cs.tsinghua.edu.cn/PGBench/index.html<br><br>
Before we do so, we should first make sure to comment-out any printing...also let's point out that I forgot to take care of comments in the corresponding article, and that having zero g2-components and so g2Count = 0, would cause an indexing error. So, we have to tweak the following things:<br>
<pre><code>...<br><br>
# read netlist
for line in file:
# split line
parts = line.split()<r>
# <strong>comment or option</strong>
if(parts[0][0] == '*' or parts[0][0] == '.'):
continue<br><br>
...<br><br>
# <strong>Group 2 component index</strong>
if(g2Count > 0 ):
g2Index = matrixSize - g2Count
else:
g2Index = 0<br>
...</code></pre><br>
Running thupg1.spice we get:<br>
https://i.postimg.cc/PrH24SH1/image.png<br><br>
Not much information out of this, but still running it is impressive! It took up most of my computer's RAM, but before this optimization I couldn't run it at all, which tells something I think!
<hr>
<h2>RESOURCES</h2>
<h3>References:</h3>
<ol>
<li>https://scipy-lectures.org/advanced/scipy_sparse/coo_matrix.html</li>
<li>https://scipy-lectures.org/advanced/scipy_sparse/csr_matrix.html</li>
<li>https://scipy-lectures.org/advanced/scipy_sparse/csc_matrix.html</li>
<li>https://scipy-lectures.org/advanced/scipy_sparse/solvers.html</li>
<li>https://docs.scipy.org/doc/scipy/reference/sparse.html</li>
</ol>
<br>
Mathematical Equations were made using <a href="https://www.quicklatex.com/">quicklatex</a>
<hr>
<h2>Previous parts of the series</h2>
<h3>Introduction and Electromagnetism Background</h3>
<ul>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-introduction-python">Introduction</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-electromagnetism-background-part-1-python">Electromagnetism Background (part 1)</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-electromagnetism-background-part-2-python">Electromagnetism Background (part 2)</a></li>
</ul>
<h3>Mesh and Nodal Analysis</h3>
<ul>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-mesh-analysis-python">Mesh Analysis</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-nodal-analysis-python">Nodal Analysis</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-modified-mesh-analysis-by-inspection-python">Modified Mesh Analysis by Inspection</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-modified-nodal-analysis-by-inspection-python">Modified Nodal Analysis by Inspection</a></li>
</ul>
<h3>Modified Nodal Analysis</h3>
<ul>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-incidence-matrix-and-modified-kirchhoff-laws-python">Incidence Matrix and Modified Kirchhoff Laws</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-modified-nodal-analysis-part-1-python">Modified Nodal Analysis (part 1)</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-modified-nodal-analysis-part-2-python">Modified Nodal Analysis (part 2)</a></li>
</ul>
<h3>Static Analysis</h3>
<ul>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-static-analysis-implementation-part-1-python">Static Analysis Implementation (part 1)</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-static-analysis-implementation-part-2-python">Static Analysis Implementation (part 2)</a></li>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-static-analysis-implementation-part-3-python">Static Analysis Implementation (part 3)</a></li>
</ul>
<h3>Sparse Matrix Optimization</h3>
<ul>
<li><a href="https://steemit.com/utopian-io/@drifter1/electronic-circuit-simulation-sparse-matrix-optimization-part-1-python">Sparse Matrix Optimization (part 1)</a></li>
</ul>
<hr>
<h2>Final words | Next up on the project</h2> And this is actually it for today's post and I hope that you enjoyed it!<br><br>
The articles from now on will be about <strong>Transient Analysis</strong> and "component extensions"...<br><br>
So, see ya next time!
<hr>
<h2>GitHub Account:</h2>
https://github.com/drifter1<br>
https://steemitimages.com/0x0/https://media.giphy.com/media/ybITzMzIyabIs/giphy.gif
<br>
Keep on drifting! ;)
</html>