Matrix Representations

Representing the Matrix

Before we can start solving a system of linear equations, we need to represent it in a way a computer can understand. We'll be using C++ to build a digital version of an augmented matrix. For a system of equations like this:

\begin{alignedat}{1} \\ 2x + 4y - 2z &= 2 \\ 4x + 9y - 3z &= 8 \\ -2x - 3y + 7z &= 10 \\ \end{alignedat}

The corresponding augmented matrix combines the coefficients and the constants into a single grid. The coefficients form the matrix $A$ , the constants form the vector $b$ , and the augmented matrix is written as $[A|b]$ .

\left[\begin{array}{ccc|c} \\ 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \\ \end{array}\right]

In C++, the most intuitive way to store this is with a vector of vectors.

#include <vector>

// A 3x4 matrix for our 3-equation system
std::vector<std::vector<double>> matrix = {
    {2.0, 4.0, -2.0, 2.0},
    {4.0, 9.0, -3.0, 8.0},
    {-2.0, -3.0, 7.0, 10.0}
};

This approach is easy to read. matrix[i][j] maps directly to the element at row i and column j. But it comes with a hidden performance cost. Each inner vector is a separate object in memory, potentially scattered across different locations. This can be slow for very large matrices due to something called cache misses when the CPU has to fetch data from far-flung memory addresses.

Optimizing for Performance

For high-performance numerical computing, it's better to store the matrix in a single, contiguous block of memory. We can achieve this using a single std::vector<double>. This guarantees all the data is laid out sequentially, which is much friendlier to modern CPU caches.

To do this, we need a way to map our familiar 2D coordinates (row, column) to a 1D index. The most common method for this is row-major ordering, where we lay out the matrix one full row at a time. C and C++ arrays follow this convention by default.

With this mapping formula, we can create a simple class to wrap our 1D vector and provide a more convenient 2D-style access.

#include <vector>
#include <iostream>

class Matrix {
private:
    std::vector<double> data; // The 1D data store
    int n_rows; // Number of rows
    int n_cols; // Number of columns

public:
    Matrix(int rows, int cols) : n_rows(rows), n_cols(cols) {
        data.resize(rows * cols);
    }

    // Overload () operator for 2D-like access
    double& at(int r, int c) {
        // index = row * num_cols + col
        return data[r * n_cols + c];
    }
};

This Matrix class gives us the best of both worlds: efficient, contiguous memory storage and an intuitive way to access elements. The at function handles the index conversion for us. For an $n$ -by- $n$ system, our augmented matrix will have $n$ rows and $n+1$ columns.

Putting It All Together

Now let's build a small program that initializes our augmented matrix from user input. This structure is what we'll use as the foundation for our Gaussian elimination solver.

#include <iostream>
#include <vector>

class Matrix {
private:
    std::vector<double> data;
    int n_rows;
    int n_cols;
public:
    Matrix(int rows, int cols) : n_rows(rows), n_cols(cols) {
        data.resize(rows * cols);
    }
    double& at(int r, int c) {
        return data[r * n_cols + c];
    }
    // ... we will add more methods later
};

int main() {
    int n; // Number of equations
    std::cout << "Enter the number of equations: ";
    std::cin >> n;

    // Create an n x (n+1) augmented matrix
    Matrix augmented_matrix(n, n + 1);

    std::cout << "Enter the coefficients of the augmented matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n + 1; ++j) {
            std::cin >> augmented_matrix.at(i, j);
        }
    }

    // At this point, the matrix is ready for elimination
    std::cout << "Matrix initialized successfully!\n";

    return 0;
}

With this code, we have a memory-efficient container that can store any $n$ -by- $n$ system of equations. Accessing coefficients and swapping entire rows, which are key operations in , becomes straightforward. We now have the digital foundation needed to begin the forward elimination phase.

Quiz Questions 1/5

For a system of linear equations with 4 equations and 4 variables, what are the dimensions of its corresponding augmented matrix?

Quiz Questions 2/5

What is the primary performance drawback of representing a large matrix using a std::vector<std::vector<double>> in C++?

Next, we'll implement the first stage of the algorithm: forward elimination.

Advanced Gaussian Elimination in C++

Advanced Gaussian Elimination in C++

Matrix Representations

Representing the Matrix

Optimizing for Performance

Putting It All Together