Circuit Solver: Solving Systems of Linear Equations

One nice feature of CMax is that it lets us simulate circuits before building them. However, simulating in CMax requires creating a protoboard layout; often, we may be interested in simulating a circuit without having to first generate a protoboard layout, particularly in the case of more complicated circuits. In this section, we will develop a framework for simulating circuits.

1) Getting Started

Template code for this exercise (and those that follow) is available in zip format here. You should do your work in these files and save it on your computer, as some of the following exercises (both this week and next) will build on this work.

2) Human vs. Machine

In our approach to solving circuits, we were able to take advantage of our human intuition about circuits, and to leverage many common patterns (resistor combinations, voltage dividers, etc). When we are programming the computer to solve circuits, it will not be able to so easily take advantage of that intuition.

However, while solving large systems of equations is very difficult for humans, computers have little trouble with it. Thus, while our human approach to solving circuits relied heavily on intuition, our computational approach will simply involve setting up a system of linear equations and letting the computer solve for it.

It is important that even though this method works, it should only be used as a last resort by humans because humans are bad (and slow) at algebra.

3) Specifying and Solving Systems of Linear Equations

Before we can get to implementing our generic circuit solver, we will need a way of representing and solving systems of linear equations in Python. We have provided part of one such representation in le.py and gauss.py. In this exercise and the next, you will complete this definition.

Consider the problem of finding values for x and y that satisfy the two equations:

You would probably approach this with the substitution method, in which you solve the second equation for x, getting x = \frac{2}{5}y + \frac{3}{5}, and then substituting that into the first equation, getting

Then, solving for y yields y = 6, and substituting y = 6 into the x expression yields x = 3.

Solving two equations in two unknowns is easy, but humans are not generally good at solving larger systems of the type that we will encounter when solving circuits in this way. Therefore, we will use a computer.

We could try to write a computer program to perform the substitution method, but this method is complicated and computationally inefficient. By contrast, Gaussian elimination is efficient and relatively easy to implement on a computer.

In this exercise, you will implement Gaussian Elimination, as well as an more natural interface for representing and solving systems of linear equations.

4) Gaussian Elimination

In this section, we will describe the Gaussian Elimination algorithm for solving systems of linear equations. This algorithm works by manipulating systems of linear equations represented as matrix operations.

The example set of linear equations can be represented by the following matrix equation:

The goal of the algorithm is to solve for the middle vector \left[\begin{array}{c}x\\ y\end{array}\right].

Generally, we will say that we are solving the equation Ax = b, where A is a square matrix of coefficients, x is a vector of variables (to be solved for), and b is a vector containing the solutions to the linear equations.

4.1) Matrices in Python

In order to work with matrices in Python, we will need a way to represent matrices and vectors in Python. While packages exist that provide very efficient representations of matrices, we will use a simpler representation; we will represent matrices as lists of lists of numbers, where each internal list represents one row of the matrix. For example, we can represent the matrix A from above as:

A = [[3, 4], [5, -2]]

Accessing the element in row i and column j can then be performed as follows:

A[i][j]

Note that A[i] refers to the list representing the i^{\text{th}} row, and so A[i][j] refers to the element at index j in that list (the element in column j). Because we are dealing with Python lists, we will say that the top row is row 0, and the left-most column is column 0.

We will represent the vector b slightly differently: we will represent it as a single list of numbers. For example, we can represent the vector b from above as follows:

b = [33, 3]

4.2) Row-echelon Form

A crucial part of the algorithm is a step called forward elimination, which converts the matrix A into row-echelon form. If a matrix is in row-echelon form, that means that reading from left to right, each row will start with at least one more zero term than the row above it.

We can do this by applying the following algorithm (described in pseudocode). Note that, below, we use the notation A_{ij} to denote the value in row i and column j in matrix A, and b_i to denote the value in position i in the vector b.

• If A is not square (if it has a different number of equations and unknowns), or if A and b have a different number of rows, return None to indicate that the system is not well specified.
• For each value c between 0 and w-1, inclusive, where w is the number of columns in A:
  • Find the row s\geq c in A whose c^\text{th} element has the highest magnitude.
    • If A_{sc} is 0, there is no unique solution to this system (your code should retun None in this case).
    • Otherwise, swap row s with row c in matrix A, and swap values s and c in vector b.
  • (After the swap described above), for each row j>c, substract off a scaled version of row c, scaled by a constant factor x chosen so as to make A_{jc} = 0 (don't forget to modify b accordingly, as well!).

4.3) Back-solving For Variables

Once the matrix A has been converted to row-echelon form, it is possible to back-solve for the values of each of the variables in the vector x.

Starting from the bottom row A, notice that only one variable has a non-zero coefficient associated with it in that equation. Thus, we can use it (and the corresponding value in b) to solve for that variable.

Once we know that variable's value, we can use that, along with the next row from the bottom in A, to solve for the next variable. We can repeat this procedure for each row in A (from each row, we should be able to determine the value of one more variable).

4.4) Putting It Together

In gauss.py, implement this entire algorithm in a function called gauss_solve(A, b), which takes a list of lists representing the matrix A and a list of numbers representing the vector b, and returns a list of numbers representing the values for x after solving.

You may find it helpful to split this function up into two pieces, and to write a smaller function for each of these subproblems:

• You could, for example, implement the forward elimination step in a function forward_elimination(A, b) This function could return new values A and b representing the values of A and b after this conversion.

• You could also implement the back-solving procedure as back_solve(A, b). This function could take in values of A and b after the forward elimination and could return a list representing the solution to the system of equations.

4.5) Examples

A few examples of this entire procedure can be found here.

4.6) Submission

Upload your gauss.py file below for checking. Note that not all of our test cases are displayed for you. You may wish to use a web search to find additional examples (potentially with solutions) to use to test your code.

Upload your gauss.py: Select File  No file selected