Data Structures and Algorithms with C · Lecture Notes

Chapter 5: Polynomials and Sparse Matrices

The value of a data structure depends on how it stores the same information in memory. These notes make that point with two familiar mathematical objects: the polynomial and the matrix. In both, most values may be zero. Of the one hundred and one coefficients of 5x100 + 1, only two are nonzero. In the large matrices of scientific computing, the nonzero entries can be fewer than one in a thousand. A representation that stores every zero wastes both memory and time. The notes first store a polynomial as a coefficient array and as a term array, add two sorted term arrays by merging them, and multiply polynomials with linked lists. Then they represent a sparse matrix with triples, transpose it in two ways, and multiply two sparse matrices. The last part introduces compressed sparse row storage and the linked sparse matrix. Every program is given in C, traced step by step, and its cost is derived with a justification.

Learning outcomes

Choosing a representation
Compare the coefficient array and the term array for polynomials in terms of memory and time.
Merge logic
Add two sorted term arrays with padd in O(n + m) time and prove this bound.
Multiplication with linked lists
Multiply polynomials with a linked list: combine terms with equal exponents, delete zero terms, and return the memory.
Sparse matrices
Store a matrix as ⟨row, column, value⟩ triples and compute at what density this representation pays off.
Transposing
Trace transpose and fast_transpose; compare their costs of O(cols · terms) and O(cols + terms).
Multiplying
Build and analyze sparse matrix multiplication with the help of the transpose; recognize compressed sparse row storage.

5.1The polynomial abstract data type

The polynomial is familiar from high-school mathematics, and it turns up often in computing: error-detecting codes, cryptography, curve fitting and numerical integration all work with polynomials. To use this object in a program we first fix the operations we need, and then choose a memory layout that makes those operations fast. The first step is the definition of an abstract data type (ADT). An abstract data type describes the values of a data type and the operations on those values, but does not say how they are stored in memory. The memory layout is chosen in the second step, the implementation.

5.1.1Polynomial, term and degree

Definition 5.1

A polynomial is an expression of the form A(x) = anxn + … + a1x + a0. Each piece aixi is a term; ai is the coefficient of the term and i is its exponent. The degree of the polynomial is the largest exponent with a nonzero coefficient. At the abstract level, a polynomial is a set of ⟨exponent, coefficient⟩ pairs in which each exponent occurs at most once.

The set view in the definition is important. The polynomial A(x) = 3x20 + 2x5 + 4 is the set {⟨20, 3⟩, ⟨5, 2⟩, ⟨0, 4⟩}. Terms with zero coefficients do not enter the set: every term from x19 down to x6 has coefficient zero, and none of them is written. The degree of the polynomial is 20. The constant term 4 = 4x0 has exponent 0. A polynomial with no terms at all is the zero polynomial; it corresponds to the empty set.

The rule that an exponent may not occur twice is also the basic condition for the addition and multiplication code. An expression like 2x3 + 5x3 does not fit the set view; the two terms must be reduced to a single term 7x3. This reduction is what the multiplication code spends most of its effort on.

5.1.2Operations

The textbook by Horowitz and coauthors defines the polynomial abstract data type with the operations in Table 5.1. The operation names are the names used in the book.

Table 5.1: Operations of the polynomial abstract data type.
OperationMeaning
Zero(), IsZero(p)constructs the zero polynomial / tests whether p is the zero polynomial
Coef(p, e)returns the coefficient of the term with exponent e; 0 if there is no such term
LeadExp(p)returns the largest exponent, that is, the degree
Attach(p, c, e), Remove(p, e)adds the term c·xe / removes the term with exponent e
SingleMult(p, c, e)returns the product p · c·xe
Add(p1, p2), Mult(p1, p2)returns the sum / the product of two polynomials

This list covers everything one does with polynomials. Add and Mult can be written with the other operations. Addition proceeds by comparing the largest exponents of the two polynomials with LeadExp and appending the appropriate term to the result with Attach. Multiplication calls SingleMult for each term of the first polynomial and adds the partial results. This is where the abstract data type pays off. The addition algorithm can be written without knowing whether the polynomial lives in memory as an array or as a linked list. A programmer who changes the implementation rewrites only these operations.

5.1.3Rules for addition and multiplication

In addition, the coefficients of terms with equal exponents are added:

A(x) + B(x) = Σ (ai + bi) · xi

If an exponent occurs in only one polynomial, the coefficient of the other polynomial at that exponent counts as 0 and the term passes to the result unchanged. If the sum of two coefficients is 0, the term drops out of the result. For example, (4x3 + 2x2 + 5) + (3x3 − 2x2 + x) = 7x3 + x + 5; the x2 terms cancel.

In multiplication, every term is multiplied by every term of the other polynomial. When two terms are multiplied, the exponents add and the coefficients multiply: aixi · bjxj = aibj xi+j.

A(x) · B(x) = Σi ( aixi · Σj bjxj )

Multiplying a polynomial of n terms by a polynomial of m terms produces n · m products. Some of these products may have the same exponent. The product (x + 1)(x − 1) produces four terms: x2, −x, x and −1. The middle two terms have exponent 1; their sum is 0, so both vanish and the result is x2 − 1. The real difficulty of the multiplication code is finding the terms with equal exponents, combining them, and discarding those that cancel.

5.2Storing a polynomial in an array

The easiest way to store a polynomial in C is an array. But there are two different choices for what the array holds: reserve one cell for every exponent, or write down only the terms that exist. For the same polynomial, these two choices lead to very different memory and time costs.

5.2.1First method: the coefficient array

The first method keeps all coefficients in an array indexed by exponent. coef[i] is the coefficient of xi:

#define MAX_DEGREE 101   /* max degree + 1 */
typedef struct {
  int degree;               /* largest exponent */
  float coef[MAX_DEGREE];   /* coef[i]: coefficient of x^i */
} polynomial;
polynomial P;

The macro MAX_DEGREE is one more than the largest degree; an array of 101 cells holds the exponents 0 through 100. The degree field of the structure stores the largest exponent with a nonzero coefficient. Thanks to this field, the array need not be scanned from the end every time the degree is requested. The typedef gives the structure the name polynomial; the line polynomial P; declares a variable of this type.

The operations are very simple in this representation. Coef(p, e) is just p.coef[e] and takes O(1). LeadExp(p) is p.degree. Addition adds the cells with the same index in the two arrays. Here is a short function that shows addition with coefficient arrays:

/* addition with coefficient arrays: d = a + b */
void array_add(const polynomial *a, const polynomial *b,
               polynomial *d) {
  int i, n = a->degree > b->degree ? a->degree : b->degree;
  for (i = 0; i <= n; i++) {
    float x = i <= a->degree ? a->coef[i] : 0;
    float y = i <= b->degree ? b->coef[i] : 0;
    d->coef[i] = x + y;
  }
  d->degree = n;
  while (d->degree > 0 && d->coef[d->degree] == 0)
    d->degree--;                /* drop leading zeros */
}

The function loops up to the larger of the two degrees. Once a polynomial's degree is exceeded, its coefficient is taken to be 0. The degree of the sum is first set to n; then the leading zeros are dropped. In the sum (2x3 + 1) + (−2x3 + x + 4) the coefficient of x3 comes out 0 and the last loop lowers the degree from 3 to 1; the result is x + 5. The running time is proportional to the larger of the two degrees: O(max(deg A, deg B)).

The problem is memory. Terms with coefficient 0 are stored too. The polynomial P(x) = 5x100 has a single term, but the array reserves 101 cells and all of coef[0..99] are 0 (Figure 5.1). Since a float is 4 bytes, this structure occupies 408 bytes together with the degree field. The meaningful information is only two numbers: the exponent 100 and the coefficient 5. Addition carries the same waste over into time: adding two one-term polynomials walks through 101 cells.

00102030405060…9901005P(x) = 5x¹⁰⁰: coef[0..99] hold needless zeros: 101 floats, 1 meaningful
Figure 5.1: The coefficient array of the polynomial 5x100. Of the one hundred and one cells only the last is meaningful; the rest store zeros for nothing.

The coefficient array has one more limit. The degree cannot exceed MAX_DEGREE − 1. For a polynomial with a term x1000 the array must have one thousand and one cells; then every polynomial, even a one-term one, occupies four kilobytes. For a sparse polynomial, that is, one in which most coefficients are 0, this method is unsuitable. If most coefficients are nonzero, as in x4 + 3x3 − x2 + 2x + 7, the coefficient array is both simple and fast.

5.2.2Second method: the term array

The second method stores only the nonzero terms. Each term is a coefficient–exponent pair. The terms of all polynomials sit in a single shared array:

#define MAX_TERMS 101   /* max number of terms */
typedef struct {
  float coef;            /* coefficient */
  int expon;             /* exponent */
} polynomial;
polynomial P[MAX_TERMS]; /* all polynomials live here */
int avail = 0;           /* first free slot */

The structure is again named polynomial, but now it represents a single term: coef holds the coefficient and expon the exponent. The array P holds the terms of all polynomials in the program. The variable avail points to the first free slot in the array; a new term is always written to P[avail] and avail is incremented.

A polynomial is a contiguous range in P. Two indices are enough to locate it: the index of its first term, start, and the index of its last term, finish. The terms are kept sorted from the largest exponent to the smallest. This order is the key to the speed of the addition algorithm. Figure 5.2 shows where the polynomials A(x) = 3x20 + 2x5 + 4 and B(x) = x5 + 10x3 + 3x2 + 1 sit in the shared array.

coefexpon[0]320[1]25[2]40[3]15[4]103[5]32[6]10[7][8]▲ sA▲ fA▲ sB▲ fB▲ avail
Figure 5.2: The shared array P holding the terms of two polynomials. A sits in P[0..2] (sA = 0, fA = 2), B in P[3..6] (sB = 3, fB = 6); the first free slot is avail = 7.

In this representation the polynomial 5x100 occupies a single cell: ⟨5, 100⟩. A term consists of a float coefficient and an int exponent and takes 8 bytes. Eight bytes suffice instead of the 408 bytes of the coefficient array. There is also no upper bound on the degree; the exponent can take any value that fits in an int. What is limited is the total number of terms of all polynomials: MAX_TERMS = 101.

An analogy explains the value of sorted terms. To turn two alphabetically sorted student lists into one sorted list, it is enough to walk down both lists at once. At each step, whichever of the two heads comes first is written to the new list. If the lists were unsorted, we would have to scan the whole other list for every name. This two-pointer walk is called merging. The course instructor stresses the same point: merge logic makes it possible to build more efficient algorithms on sorted structures. Polynomial addition rests entirely on this idea.

5.2.3Comparing the two representations

Which representation is better depends on the structure of the polynomial. Table 5.2 compares the two in terms of memory and basic operations. In the table, d is the degree and t is the number of nonzero terms.

Table 5.2: Comparison of the coefficient array and the term array.
CriterionCoefficient arrayTerm array
MemoryMAX_DEGREE cells (fixed)t terms (8 bytes each)
Coef(p, e)O(1)O(t) (or O(log t) with binary search)
LeadExp(p)O(1) (degree field)O(1) (first term)
AdditionO(d)O(tA + tB)
Degree limitMAX_DEGREE − 1none (only the total term limit)
Suitable fordense, low-degree polynomialssparse polynomials

In the term array Coef becomes slower, because the requested exponent must be searched for in the array. But most polynomial operations walk through the terms in order instead of querying coefficients one by one. Addition and multiplication are such operations, and on the term array they take time proportional to the number of terms. Adding 3x20 + 2x5 + 4 with coefficient arrays walks through 21 cells; with the term array 3 terms are enough.

Common mistake

Writing a term with a zero coefficient into the term array, or adding the same exponent twice. All algorithms of this representation assume that every exponent occurs at most once and that the coefficients are nonzero. A term like 0x5 wastes space, reports the wrong degree and breaks the IsZero test: a polynomial whose only term is 0 is the zero polynomial, yet it does not look empty.

5.3Polynomial addition: padd

The function that adds two polynomials in the term-array representation is called padd (polynomial add). It adds A in P[sa..fa] and B in P[sb..fb] and writes the result into the free part of P, starting at avail.

5.3.1Merging with two pointers

The terms of both polynomials are sorted from the largest exponent to the smallest. The indices sa and sb point to the first unprocessed term of each polynomial; we call them pointers. They are array indices, not C pointers. At each step the exponents of the terms the two pointers point to are compared. There are three cases:

  • The exponents are equal. The coefficients are added. If the sum is nonzero, a term with this exponent is appended to the result; if it is zero, the term vanishes. Both pointers advance by one.
  • A's exponent is larger. B has no term with this exponent. All remaining terms of B have exponents no larger than B's current term, and the current term is smaller than A's. So this exponent occurs nowhere in B. A's term is appended to the result unchanged and only A's pointer advances.
  • B's exponent is larger. The case is symmetric: B's term is appended and only B's pointer advances.

When the terms of one polynomial run out, the loop stops. The exponents of the remaining terms of the other polynomial are smaller than those of all terms already written to the result; these terms are copied to the result unchanged.

The justification of the second case is the heart of the correctness of the algorithm, and it holds only because of sortedness. If the terms were unsorted, we would have to scan all of B to find out whether a term of A has a counterpart in B. In a sorted array, B's current term alone answers the question.

5.3.2COMPARE and attach

padd uses two helpers. The first is a macro that performs a three-way comparison, the second is a function that appends a term to the result:

#define COMPARE(x, y) \
  ((x) < (y) ? -1 : (y) < (x) ? 1 : 0)

void attach(float coef, int expon) {
  if (avail >= MAX_TERMS) {
    fprintf(stderr, "Array overflow!\n"); exit(1);
  }
  P[avail].coef = coef;
  P[avail++].expon = expon;
}
#define APPEND(k) attach(P[k].coef, P[k].expon)

COMPARE(x, y) yields −1 if x < y, 1 if x > y, and 0 if they are equal. It is written with two nested conditional operators. The macro parameters are parenthesized at every use because the preprocessor substitutes the macro as text. In a call like COMPARE(a + 1, b), the parentheses keep operator precedence from grouping the expression the wrong way. The three-valued result is what lets padd be written with a switch.

attach writes a term to P[avail] and increments avail. Before writing it checks whether the array is full; if so, it prints a message to the standard error stream and terminates the program. Without this check it would write to P[101]. Writing outside the bounds of an array is undefined behavior in C: neighboring variables may be corrupted or the program may crash. The line P[avail++].expon = expon; uses the postfix increment operator: first the exponent of P[avail] is written, then avail is incremented.

The macro APPEND(k) is shorthand for copying the term P[k] to the result unchanged. After preprocessing, APPEND(sb) becomes attach(P[sb].coef, P[sb].expon).

Common mistake

Declaring the coefficient parameter of attach as int: void attach(int coef, int expon). Then a float coefficient is truncated to an integer as it is passed to the function, and the coefficient 2.5 becomes 2. The compiler performs this conversion on its own; it gives no warning even with -Wall -Wextra. A warning appears only with the -Wconversion option. The type of the parameter must match the type of the field it is stored in: float coef.

5.3.3The padd() code

void padd(int sa,int fa,int sb,int fb,int*sd,int*fd){
  float c; *sd = avail;               /* start of D */
  while (sa <= fa && sb <= fb)
    switch (COMPARE(P[sa].expon, P[sb].expon)) {
    case -1: APPEND(sb); sb++; break;     /* B larger */
    case  1: APPEND(sa); sa++; break;     /* A larger */
    case  0: c = P[sa].coef + P[sb].coef;
      if (c) attach(c, P[sa].expon); /* 0: skip */
      sa++; sb++;
    }
  for (; sa <= fa; sa++) APPEND(sa);   /* rest of A */
  for (; sb <= fb; sb++) APPEND(sb);   /* rest of B */
  *fd = avail - 1;
}

The function takes six parameters. The first four are the input ranges: A sits in P[sa..fa] and B in P[sb..fb]. The last two are outputs: sd and fd are the addresses of the variables that receive the start and end indices of the result. A C function can return only one value. To return two values, the caller passes the addresses of two variables and the function writes to those addresses. The expression *sd = avail; stores the current value of avail in the caller's variable.

The structure of the code is as follows:

  1. Line 2: The first term of the result will be written to P[avail], so *sd is fixed right away.
  2. Lines 3–10: The loop runs as long as both polynomials have terms left. The switch picks one of three branches according to the comparison of the exponents. case -1 appends the term of B when B's exponent is larger. case 1 appends the term of A. case 0 adds the coefficients; if the sum is not 0, attach is called. The condition if (c) means c != 0.
  3. Lines 11–12: When the loop ends, at most one of the two polynomials has terms left. Only one of the two for loops does any work; the other finds its condition false from the start.
  4. Line 13: The last term appended is in P[avail − 1]; *fd receives this index.

The case 0 branch has no break at its end. Since this is the last branch of the switch, control falls out of the switch anyway; it does not run into another branch. Still, writing a break in the last branch too is a good habit: if a new branch is added below it later, the code will not flow into it by accident.

5.3.4Code trace: A + B

The polynomial A(x) = 4x3 + 2x2 + 5 sits in P[0..2], B(x) = 3x3 − 2x2 + x sits in P[3..5], and avail = 6 (Figure 5.3). The call padd(0, 2, 3, 5, &sd, &fd) proceeds as in Table 5.3.

coefexpon[0]43[1]22[2]50[3]33[4]-22[5]11[6][7][8][9]▲ sa▲ sb▲ avail
Figure 5.3: The start of padd. sa = 0 points to the first term of A, sb = 3 to the first term of B; the result will start at avail = 6.
Table 5.3: Trace of padd(0, 2, 3, 5, &sd, &fd).
StepsasbExponentsCOMPAREActionavail
003——*sd = 66
1033, 30c = 4 + 3 = 7; attach(7, 3): P[6] = 7x³; both advance7
2142, 20c = 2 + (−2) = 0; not appended; both advance7
3250, 1−1APPEND(5): P[7] = 1x¹; only sb advances8
426——sb = 6 > fb = 5: the loop ends8
536——rest of A: APPEND(2): P[8] = 5x⁰9
636——*fd = 9 − 1 = 89

In the table, the sa and sb columns show the values at the start of the step, and the avail column shows the value at the end of the step. In the first two rounds the exponents are equal. In the first, the coefficients are added and 7x3 is written. In the second, 2x2 and −2x2 cancel; since c is zero, attach is not called and avail does not change. In the third round the remaining term of A is 5x0 and that of B is x1. Because COMPARE(0, 1) = −1, the term of B is appended. After this step B is exhausted and the loop condition becomes false. The remaining 5 of A is copied by the first for loop.

coefexpon[0]43[1]22[2]50[3]33[4]-22[5]11[6]73[7]11[8]50[9]▲ avail
Figure 5.4: When padd finishes: the result D(x) = 7x3 + x + 5 sits in P[6..8] and avail = 9. The faded cells are the input polynomials.

The result is D(x) = 7x3 + x + 5 and it occupies P[6..8]: sd = 6, fd = 8. When the program is run on this input, attach is called three times and avail becomes 9. The input polynomials stay where they are; padd does not modify them.

Example 5.1

Adding the polynomials of Figure 5.2: A = 3x20 + 2x5 + 4 (P[0..2]), B = x5 + 10x3 + 3x2 + 1 (P[3..6]), avail = 7.

  1. 20 versus 5: A is larger; 3x20 → P[7].
  2. 5 versus 5: equal; 2 + 1 = 3, 3x5 → P[8].
  3. 0 versus 3: B is larger; 10x3 → P[9].
  4. 0 versus 2: B is larger; 3x2 → P[10].
  5. 0 versus 0: equal; 4 + 1 = 5 → P[11]. Both polynomials are exhausted; the remaining copy loops do nothing.

The result is 3x20 + 3x5 + 10x3 + 3x2 + 5 and it sits in P[7..11]. The loop runs five rounds and makes five attach calls. With coefficient arrays the same addition would walk through 21 cells.

5.3.5Complexity

Theorem 5.1 (Cost of padd)

If A has n terms and B has m terms, padd runs in Θ(n + m) time and writes at most n + m terms.

Upper bound. In every round of the while loop, at least one of sa and sb increases by one. sa can increase at most n times and sb at most m times. So the loop runs at most n + m rounds. The two for loops that copy the remaining terms after the loop increment the same pointers. The total increase of the pointers cannot exceed n + m. So the total number of rounds of all loops is also at most n + m. Each round does a constant amount of work (one comparison, at most one addition and one attach). The time is O(n + m).

Lower bound. Each round advances at most two pointers by one each. For all terms to be processed, the pointers must advance n + m times in total; that means at least (n + m)/2 rounds. The time is Ω(n + m). Together the two bounds give Θ(n + m). □

The best case is when all exponents are shared (n = m). Every round enters case 0 and both pointers advance together; the loop runs n rounds. The cost is then Ω(n); since n = m, this is of the same order as Θ(n + m). The worst case is when there is no common exponent. Then every term is written separately and n + m calls to attach are made. That is why adding two ten-term polynomials makes at most 20 calls to attach. This count has also been verified by a program. Adding a ten-term polynomial with odd exponents to a ten-term polynomial with even exponents counts 20 calls. Adding two identical polynomials counts 10 calls.

What would happen if the terms were kept unsorted? For each term of A we would have to search B for a term with the same exponent, and if none were found, put the term in the right place in the result. The search takes O(m) per term and O(nm) for n terms. If insertions are used to keep the result sorted, every insertion shifts the terms in the array, and the total rises to the order of O((n + m)2). As the instructor puts it, if O(n + m) is what we want and we can do better, so much the better. But since every term of the input must be looked at at least once, no algorithm for addition can be faster than n + m; padd is of optimal order.

5.3.6The price of the shared array

The shared array P is a simple memory manager: avail only moves forward. Every call to padd appends its result to the end of the array. The terms of a polynomial that was only needed as an intermediate result stay in the array, and their space is not reclaimed. In a long computation the array fills up with such leftovers and attach stops the program with the message “Array overflow!”, even though the live polynomials in the array may be small in total.

There are two solutions to this problem. The first is compaction. When the array is full, the polynomials still in use are shifted toward the start of the array and their start and end indices are updated. Compaction takes time proportional to the number of live terms and must be written carefully because it changes the indices of all polynomials. The second solution is to store the polynomial as a linked list. Each term sits in its own node; a node that is no longer needed is returned at once with free.

5.4Multiplication on arrays and operations on many polynomials

padd adds two polynomials. Multiplication, and the sum and product of many polynomials, can also be written with the same array representation. The solutions to these three problems, which the slides leave as homework, are given in detail below.

5.4.1pmult(): multiply by one term and add

The multiplication rule suggests an algorithm. For each term aixei of A, multiply B by this single term (SingleMult). The resulting polynomial of m terms is added to the partial result with padd. Since the terms of B are sorted, the product with a single term is also a sorted polynomial: the same ei is added to every exponent and the order is preserved. The function written in these notes as the solution of the homework is the following:

/* A = P[sa..fa], B = P[sb..fb]; product P[*sd..*fd] */
void pmult(int sa, int fa, int sb, int fb,
           int *sd, int *fd) {
  int i, j, ss = avail, sf = avail - 1;  /* empty partial */
  int ts, tf, ys, yf;
  for (i = sa; i <= fa; i++) {
    ts = avail;                      /* B · a_i x^e_i */
    for (j = sb; j <= fb; j++)
      attach(P[i].coef * P[j].coef,
             P[i].expon + P[j].expon);
    tf = avail - 1;
    padd(ss, sf, ts, tf, &ys, &yf);  /* add to partial */
    ss = ys;  sf = yf;
  }
  *sd = ss;  *fd = sf;
}

The partial result is P[ss..sf]. It starts out empty: since sf = ss − 1, the range contains no terms. In each round of the outer loop, B · aixei is written between ts and tf. Then padd adds the old partial result to this temporary polynomial and puts the new partial result at the end of the array. In the first round the partial result is empty, so the main loop of padd never runs and the temporary polynomial is simply copied.

Example 5.2

A = x + 1 in P[0..1], B = x − 1 in P[2..3]; avail = 4, the partial result is empty (ss = 4, sf = 3).

  1. i = 0 (term x): x · B = x2 − x → P[4..5]. padd(4, 3, 4, 5) adds it to the empty partial result; the new partial result is P[6..7] = x2 − x.
  2. i = 1 (term 1): 1 · B = x − 1 → P[8..9]. padd(6, 7, 8, 9): x2 is appended, −x + x = 0 is skipped, −1 is copied. The partial result is P[10..11] = x2 − 1.

The function returns sd = 10, fd = 11 and avail becomes 12. Of the twelve positions only two hold the result; P[4..9] are now unused intermediate polynomials.

For the time analysis, let A have n terms and B have m terms. In round i the temporary polynomial has m terms and is written in O(m) time. The partial result has at most i · m terms, since i · m products have been produced so far. padd takes O(im + m) time in this round. Summed over all rounds:

Σi=1n O(im + m) = O(m · n(n + 1)/2 + nm) = O(n2m)

The form O(n · (nm + m)) = O(n2m) in the slides reaches the same result by bounding the partial result in every round by its largest size, nm. The result is not symmetric: n appears squared and m to the first power. If the smaller polynomial is put in the outer loop, the cost is O(min(n, m)2 · max(n, m)). Suppose a polynomial of 2 terms is multiplied by a polynomial of 100 terms. Putting the two-term one outside does about 22 · 100 = 400 units of work; the reverse does 1002 · 2 = 20,000 units.

The memory cost is even worse. Each round writes m temporary terms and at most im new partial-result terms, and none of them is returned. The total consumption is also O(n2m). This price of the shared array makes compaction or a linked list necessary in long computations. In the program, the product (3x20 + 2x5 + 4)(x5 + 10x3 + 3x2 + 1) gives the correct 11-term result, but avail rises from 7 to 42: of the 35 positions only 11 are the result.

5.4.2Adding n polynomials

A program that works with many polynomials can keep the location of each polynomial in two tables. start[k] is the index of the first term of polynomial k in P, and finish[k] is the index of its last term. The easiest way to add n polynomials is to call padd repeatedly: first the first two are added, then the third is added to the result, and so on.

Let N be the total number of terms in all the polynomials. In repeated addition the partial result grows and every padd walks over it from the beginning. In the worst case the terms of the first polynomial are copied n − 1 times. The total cost is O(n · N). For example, 100 polynomials of 100 terms each, with no shared exponents, require about 100 · 10,000 / 2 = 500,000 term copies.

A better way is to merge all n polynomials at once. One pointer is kept for each polynomial. At every step, the term with the largest exponent among the terms the n pointers point to is selected; terms with equal exponents are added. Finding the largest among n terms by a plain scan takes O(n) per step and O(n · N) in total; there is no gain. Selecting the largest exponent with a priority queue, for example a heap, brings each step down to O(log n). The total cost is O(N log n). The same result is obtained by adding the polynomials two at a time, like a tournament tree. In each round the number of polynomials halves; each round does O(N) work in total and there are ⌈log2 n⌉ rounds.

5.4.3Multiplying n polynomials

In multiplication the partial results grow quickly. If n polynomials are multiplied from left to right, the product P1P2 is multiplied by P3, that result by P4, and so on. At every step a large partial result is multiplied by a small polynomial. Since the cost of pmult grows with the square of the number of terms of the polynomial in the outer loop, the large partial result should always be put in the inner loop.

Multiplying two at a time, in a tree shape, balances the sizes. First P1P2, P3P4, … are multiplied; then these products are multiplied two at a time. At each level the polynomials being multiplied are of similar size. The same start/finish tables can be used to hold the partial results; but since leftovers pile up quickly in the array representation, a linked list is a more suitable choice.

Common mistake

Writing the product term by term directly at the end of the array without combining terms with equal exponents. If x2 − x + x − 1 is written for (x + 1)(x − 1), the array is no longer sorted and the same exponent occurs twice. Every later call to padd gives a wrong result with this polynomial, because the merge logic assumes that every exponent occurs once and in sorted order. That is why pmult adds every single-term product with padd.

5.5Polynomials as linked lists

The array representation has two weak points: the total number of terms must be known in advance, and the space of terms that are no longer needed is not reclaimed. A linked list solves both. Each term sits in a node allocated with malloc. The nodes are tied together with pointers, and the number of terms can grow and shrink freely while the program runs. When a term is no longer needed, its node is returned to the system with free.

5.5.1The node structure

typedef struct poly_node *poly_ptr;
typedef struct poly_node {
  int coef;
  int expon;
  poly_ptr link;
} poly_node;

The first line defines a pointer type to struct poly_node under the name poly_ptr. This line comes before the definition of the structure. C allows this, because declaring a pointer to a structure does not require knowing its contents; it is enough to know that the name denotes a structure. The definition that follows gives the three fields of the node: coef, expon, and link, which holds the address of the next node in the list. Because the structure contains a field that points to itself, it is called a self-referential structure. In this representation the coefficients are integers.

The list again keeps the terms in decreasing order of exponent and contains only nonzero terms. The address of the first node of the list is stored in a poly_ptr variable; the link field of the last node is NULL. Figure 5.5 shows the list of the polynomial a = 3x14 + 2x8 + 1.

coefexponlink3142810∅
Figure 5.5: The linked list of the polynomial a = 3x14 + 2x8 + 1. Each node holds a coefficient, an exponent and the address of the next node; the link of the last node is NULL (∅).

On a 64-bit system a node occupies 16 bytes: 8 bytes for the two int fields and 8 bytes for the pointer. That is twice the space of the 8-byte term in the term array; this is the price of the link. In return, the nodes need not be contiguous in memory, and there is no limit of a shared array. The number of terms of a polynomial is limited only when the system's memory runs out.

The list has two important advantages. First, insertion and deletion in the middle are done by changing just a few pointers, in O(1) time; once the position has been found, of course. In an array, insertion in the middle would require shifting all following terms by one position. Second, addition is again a merge: one walks down the heads of both lists at once and applies the three cases of padd unchanged. Addition with linked lists also runs in O(n + m) time. The only difference is that the result nodes are allocated with malloc and returned with free when the work is done.

5.5.2add_term() and delete_next()

The multiplication code relies on two helpers. The first creates a new term node and, optionally, links it after a given node:

/* create a term; if prev is given, link it after prev */
poly_ptr add_term(int expon, int coef,
                  poly_ptr prev) {
  poly_ptr p = malloc(sizeof *p);
  if (!p) { printf("Out of memory!\n"); exit(1); }
  p->expon = expon;  p->coef = coef;
  if (prev) {              /* in the middle or at the end */
    p->link = prev->link;    /* new node first */
    prev->link = p;         /* then prev */
  } else p->link = NULL;      /* standalone */
  return p;
}

malloc(sizeof *p) allocates as much memory as the type p points to, that is, poly_node. Writing sizeof(poly_node) is also correct; but the form sizeof *p stays correct on its own if the type of p changes. If malloc cannot find memory, it returns NULL. The code checks this case at once and terminates the program with a message. Without the check, the next line would try to write to the place the NULL pointer points to; that is undefined behavior and on most systems the program crashes.

After the fields of the node are filled in, two cases are distinguished. If prev is given, the new node is linked after it. The order matters: first the link of the new node is pointed at the old successor of prev, then the link of prev at the new node. If the two lines were swapped, prev->link would be overwritten with the new node first; the address of the old successor would be lost and the rest of the list would become unreachable. If prev is NULL, the new node becomes a list on its own; its link is NULL. In every case the function returns the address of the new node.

The second helper deletes the node after a given node:

/* delete the node after prev */
void delete_next(
        poly_ptr prev) {
  poly_ptr victim =
        prev->link;
  if (!victim) return;
  prev->link =
        victim->link;
  free(victim);
}

The address of the node to delete is first saved in the variable victim. Then the link of prev is pointed at the successor of the node being deleted; this takes the node out of the list. Finally the memory of the node is returned with free. If the link were updated without saving the address, the node could never be reached again and its memory could never be returned. Memory lost this way is called a memory leak. As the instructor puts it, the leftovers in memory must be cleaned up. The reverse order is also wrong: if free(prev->link) is called first and then prev->link = prev->link->link is written, the fields of a freed node are read. A pointer that points to returned memory is called a dangling pointer, and using it is undefined behavior.

If there is no node to delete (prev is the last node), the function returns without doing anything. Note that the function cannot delete the first node: deletion is always done through the previous node. The multiplication code can live with this restriction, because the first term of the product list is never deleted.

5.5.3pmult_list() and place()

In the product of two polynomials, every term of A is multiplied by every term of B. Each product produced is put in its place in the sorted result list. If a term with the same exponent already exists, its coefficient is updated; if the updated coefficient becomes 0, the term is deleted. For readability, this body of the inner loop is moved into a separate function:

poly_ptr place(poly_ptr r,
               int expon, int coef) {
  while (r->link && r->link->expon > expon) r = r->link;
  if (!r->link || r->link->expon < expon)
    add_term(expon, coef, r);          /* new exponent */
  else if ((r->link->coef += coef) == 0)
    delete_next(r);                    /* became 0 */
  return r;
}

place starts at node r and looks for the position of the new term. The assumption is that the exponent of r is larger than the exponent of the new term, that is, the new term will come somewhere after r. The while loop advances as long as the exponent of the next node is larger than the new exponent. When the loop ends, r is the last node that will come before the new term. Three cases remain:

  • If there is no node after r (!r->link), or the exponent of the next node is smaller than the new exponent, this exponent is not in the list. add_term(expon, coef, r) links the new node after r.
  • If the exponent of the next node equals the new exponent, coef is added to its coefficient. The expression (r->link->coef += coef) == 0 first performs the addition and then compares the result with 0.
  • If the sum became 0, delete_next(r) deletes that node.

The function returns r. This return value is the starting point of the next search. Since the terms of B arrive in decreasing order, the products produced with the same p are also in decreasing order. The next product comes after the position of the previous one in the list; there is no need to restart the search from the head of the list.

The multiplication function itself is the following:

poly_ptr pmult_list(poly_ptr p_head,
                    poly_ptr q_head) {
  poly_ptr p, q, r = NULL, anchor = NULL, r_head = NULL;
  for (p = p_head; p; p = p->link) {
    r = anchor;            /* start the search here */
    for (q = q_head; q; q = q->link) {
      int expon = p->expon + q->expon;
      int coef = p->coef * q->coef;
      if (r_head) r = place(r, expon, coef);
      else r_head=r=anchor=add_term(expon, coef, NULL);
      if (q == q_head) anchor = r;  /* for the next p */
    }
  }
  return r_head;
}

p_head and q_head are the heads of the lists of the two polynomials. r_head holds the head of the result list; the function returns it at the end. r is the position that walks through the result list in the inner loop. anchor is the node where the search for the next p will start.

The variable anchor rests on an observation. The product of p with the first term of B, q_head, is the term with the largest exponent that p can produce. The next term p' has a smaller exponent than p. All products of p' have exponents smaller than the product of p with q_head and cannot fall in front of it in the list. So the search for p' can start from where the product p · q_head was placed. In the code, this is done by saving in anchor the r that is returned when q == q_head. Each round of the outer loop starts with r = anchor.

While the result list is empty (r_head == NULL), place cannot be called, because r is not a valid node. In this case the first product becomes a standalone node with add_term(expon, coef, NULL), and r_head, r and anchor are all pointed at this node. In the chained assignment r_head=r=anchor=… the assignment operator works from right to left: first anchor, then r, and last r_head receives the value.

The first node of the list is the product of the first term of A and the first term of B. The exponent of this term is the largest of all products and it is obtained only once: no other pair of terms can give the same exponent. So the first node is never updated or deleted; the fact that delete_next cannot delete the first node causes no problem. For the same reason, the exponent of the node r at which a search starts is always larger than the exponent of the new term, and the assumption of place is preserved.

5.5.4Code trace: (x + 1)(x − 1)

The lists A = x + 1 and B = x − 1 have two nodes each. Nodes are written as (coefficient, exponent) pairs: A = (1, 1) → (1, 0), B = (1, 1) → (−1, 0). The expected result is x2 − 1. Table 5.4 traces each of the four products. In the table, &(1, 2) is the address of the node with coefficient 1 and exponent 2.

Table 5.4: Trace of pmult_list(A, B), A = x + 1, B = x − 1.
Stepp, qexpon, coefActionResult listr, anchor
1x, x2, 1list empty: add_term(2, 1, NULL); q == q_head → anchor = rx2&(1, 2), &(1, 2)
2x, −11, −1place: no node after r → new node −xx2 − x&(1, 2), &(1, 2)
31, x1, 1r = anchor; the next node has exponent 1 = 1 → coefficient −1 + 1 = 0 → delete_next(r); anchor = rx2&(1, 2), &(1, 2)
41, −10, −1place: no node after r → new node −1x2 − 1&(1, 2), &(1, 2)

In the first step the list is empty and the first node is created directly. In the second step place starts from r = &(1, 2). Since there is no next node, the loop never runs and the node −x is attached after x2 (Figure 5.6a). The function returns not the new node but its predecessor; r is still &(1, 2).

The third step is the interesting moment of the multiplication. The outer loop moves on to p = 1 and starts with r = anchor. In this example anchor is the first node of the list; for longer polynomials the search can start from the middle of the list. The new product is 1 · x = x. The exponent of the next node, −x, is also 1. The coefficients are added: −1 + 1 = 0. Since the term has become zero, delete_next(r) removes it from the list and returns its memory (Figure 5.6b). In the fourth step the constant term 1 · (−1) = −1 is appended at the end of the list.

coefexponlink12-11∅▲ r, anchorp: x q: −1 coefexponlink12∅▲ r, anchorp: 1 q: x
Figure 5.6: Two moments of pmult_list. (a) Step 2: the node −x has been attached after x2. (b) Step 3: when +x is added, the coefficient becomes 0 and the node is deleted; the list is again a single node.

The result is x2 − 1. n · m = 4 products were made, and −x and +x, having the same exponent, were combined and deleted. The function returns r_head. When the program is done with the result, it must return all nodes of the list one by one with free; the same holds for the inputs. The test driver has a short loop that does this: the address of the next node is saved, the current node is freed, and the saved address is moved to.

Example 5.3

Which term is deleted in the product (x2 + 1)(x2 − 1)?

  1. p = x2: x2 · x2 = x4 becomes the first node. x2 · (−1) = −x2 is attached after it. The list: x4 − x2.
  2. p = 1: the search starts from the node anchor = x4. 1 · x2 = +x2; a node with the same exponent exists and the coefficient becomes −1 + 1 = 0. The x2 term is deleted.
  3. 1 · (−1) = −1 is appended at the end.

The result is x4 − 1. The program produces the same list.

5.5.5Complexity and measurement

Let A have n terms and B have m terms. The number of products is exactly nm. The work of each product itself is constant (one addition, one multiplication, at most one malloc or free). The real cost is the walk in the while loop of place.

For one term p, the inner loop starts at anchor and only moves forward in the list. place continues from where it left off on every call and never goes back. So the total walk for one p cannot exceed the length of the list after anchor. The result list has at most nm nodes. The cost of one p is O(m + nm), and the cost of all p is O(n2m). This bound is the same as that of pmult, but the linked list spends no extra memory on partial results: the result list has at most nm nodes and nodes that become zero are returned at once.

Whether the bound is actually reached depends on the exponents of the terms. To see this, a counter was added to the loop of place and two polynomials with n = m terms were multiplied in two different arrangements. In both cases the result consists of nm terms with distinct exponents:

  • Sparse A, dense B. The exponents of A are (n − 1)m, …, m, 0; those of B are m − 1, …, 0. The products of each p form a block, and the block of the next p comes entirely after it.
  • Dense A, sparse B. The exponents of A are n − 1, …, 0; those of B are (m − 1)n, …, n, 0. The products of each p are interleaved among the earlier ones.
Table 5.5: Total number of steps of the place loop (n = m, nm terms in the result).
n = mSparse A, dense BDense A, sparse Bn2m / 2
10178502500
207584,0074,000
403,11832,01732,000
8012,638256,037256,000
16050,8782,048,0772,048,000

In the first arrangement the number of steps quadruples when n doubles; it is about 2nm, that is, O(nm). Here anchor does its job: the search for each p starts at the head of the previous block and the list is traversed only once. In the second arrangement the number of steps grows eightfold and is almost equal to n2m/2. Because the terms each p adds are scattered among the earlier terms, each p walks over most of the list again. This shows that the bound O(n2m) is actually reachable. The worst-case cost is Θ(n2m).

The practical lesson from the measurement is this: if n and m differ, the smaller polynomial should go in the outer loop. Since the square of the number of terms of the outer polynomial enters the cost, putting a 2-term polynomial outside is about fifty times cheaper than putting a 100-term one outside.

The correctness of the code was tested as well. The pmult_list results for 20,000 randomly generated pairs of polynomials were compared with a brute-force product that accumulates the coefficients in an array. Every result list was found to have decreasing exponents, no zero coefficients, and to equal the brute-force result.

Common mistake

Leaving a term whose coefficient has dropped to 0 in the list. If the product (x + 1)(x − 1) stays as the list x2 + 0x − 1, the list carries an extra node, the degree and the number of terms look wrong, and later operations visit this node needlessly. A node that becomes zero must both be removed from the list and returned with free; changing only the link leads to a memory leak.

5.5.6Other solutions to the problem

pmult_list is not the only way to multiply two polynomials. Table 5.6 gives the methods listed in the slides together with their complexities. A has n terms and B has m terms.

Table 5.6: Different solutions to polynomial multiplication.
MethodComplexity
1Multiply everything and append each product at the end; then sort and mergeO(n2m2)
2Multiply everything; for each product scan the result from the start and insert at the right positionO(n2m2)
3Build a list for the product with each term of A and merge it with the result at every stepO(n2m)
4Method 3, smaller polynomial outsideO(min(n, m)2 · max(n, m))
5A separate list for each term of A; at the end all are merged two at a timeO(m · n · lg n)
6Method 5, smaller polynomial outsideO(m · n · lg min(m, n))
7Allocate an array; index k holds the coefficient of exponent k—

The first method writes the nm products into an unsorted list, then sorts the list and combines neighboring equal exponents. If the sort is done with a simple quadratic algorithm, for example insertion sort, (nm)2 = n2m2 comparisons are needed. The second method scans the result from the start for every product; since the result can grow to nm terms, this is again O(n2m2). The third method is the list version of pmult; pmult_list also comes down to this bound thanks to anchor.

The fifth method resembles the merge phase of merge sort. n lists are produced, each with m terms. Then they are merged two at a time: n lists drop to n/2, n/2 lists drop to n/4. At each level at most nm terms are processed in total and there are ⌈lg n⌉ levels. The total cost is O(nm lg n). Building the lists from the terms of the smaller polynomial puts the small number inside the logarithm.

The seventh method accumulates the result in a coefficient array: the coefficient of each product is added to d[expon]. The multiplication itself takes O(nm) and is extremely simple. But the size of the array depends on the size of the exponents. For two sparse polynomials containing x1000000, an array of two million cells is needed. Converting the result array back into a term list also requires scanning the whole array. The course instructor gives a short and blunt answer to this idea: never an array whose n-th index holds the n-th exponent. Putting a non-sparse array inside a structure designed for sparse data gives back all the gains of the structure. The test program of these notes used the seventh method only as a correctness check, with small exponents.

5.6Sparse matrices

The problem seen with polynomials appears on a larger scale in two-dimensional structures. The adjacency matrix of a city's road network, the friendship relations in a social network, or the system of equations in an engineering simulation are matrices with thousands of rows and columns. The vast majority of their entries are zero: each junction is connected to a few junctions, and each person's number of friends is small next to the total population.

5.6.1Definition

Definition 5.2

A sparse matrix is a matrix most of whose entries are zero. The nonzero entries are called nonzero entries. There is no exact threshold for calling a matrix sparse. In practice a matrix is considered sparse if the number of nonzero entries t is a small fraction of the total number of entries, rows · cols.

Of the 36 cells of the 6 × 6 matrix in Figure 5.7, only 8 are nonzero. Most of the sparse matrix examples in these notes are derived from this matrix. In C the matrix can be stored in a two-dimensional array, int a[6][6]. This array reserves 36 cells for 8 meaningful numbers. A 1000 × 1000 matrix with only five nonzero entries in each row takes 4 MB with four-byte integers; the nonzero entries number only 5,000.

00151020322405-15101130002000-60030000004910000050028000
Figure 5.7: A 6 × 6 sparse matrix. Only 8 of the 36 cells are nonzero (dark cells).

Wasted memory is not the only problem. In a two-dimensional array, operations such as transpose, addition and multiplication walk through all cells. The transpose of a 1000 × 1000 matrix copies a million cells, although only 5,000 entries change place. The aim of sparse matrix representations is to tie both memory and running time to the number of nonzero entries.

5.6.2The triple representation

Each nonzero entry is fully determined by three pieces of information: its row, its column and its value. Gathering these three pieces in one structure is the two-dimensional counterpart of the ⟨exponent, coefficient⟩ pair of the term array.

Definition 5.3

A triple is a ⟨row, column, value⟩ record that holds one nonzero entry of a sparse matrix. In the triple representation the matrix is an array of triples. Element 0 of the array is the header: it holds the number of rows, the number of columns and the number of nonzero entries. The triples are ordered by row, and within the same row by increasing column.

#define MAX_TERMS 101
#define MAX_COL 50   /* max columns */
typedef struct {
  int row, col, value;   /* row, column, value */
} term;
term M[MAX_TERMS];

The term structure has three int fields and occupies 12 bytes. M[0] is the header: M[0].row holds the number of rows, M[0].col the number of columns, and M[0].value the number of nonzero entries. The nonzero entries are stored from M[1] to M[M[0].value]. MAX_COL is the size of the helper arrays in the transpose functions; the number of columns of the matrix cannot exceed this value. Storing the header as a triple of the same type is a small trick: no separate header structure is needed, and the matrix is passed to functions as a single array.

rowcolvalueM[0]668M[1]0015M[2]0322M[3]05-15M[4]1111M[5]123M[6]23-6M[7]4091M[8]5228
Figure 5.8: The triple table of the matrix in Figure 5.7. M[0] = (6, 6, 8) is the header; the eight triples are ordered by row, then by column.

The ordering condition is row-major order applied to triples. A two-dimensional array sits in memory row by row; the triple table reads the nonzero entries in the same order. In Figure 5.8 the three entries of row 0 (columns 0, 3, 5) come first, then the two entries of row 1 (columns 1, 2). Row 3 has no nonzero entry, so the table has no triple with row number 3. Thanks to this order, the entries of a row are consecutive in the table, and reading a row means reading a range of the table.

The book by Horowitz defines the sparse matrix abstract data type with four operations: Create(max_row, max_col) constructs an empty matrix, Transpose(a) returns the transpose, and Add(a, b) and Multiply(a, b) return the sum and the product. The triple representation is only one implementation of these operations; there are others, such as linked lists and compressed sparse row storage.

5.6.3When does the triple representation pay off?

A two-dimensional array stores rows · cols integers. The triple representation stores t + 1 triples including the header, that is, 3(t + 1) integers. For the triple representation to take less space, we need

3(t + 1) < rows · cols, that is, t < rows · cols / 3 − 1

Roughly, if less than a third of the matrix is nonzero, the triple representation pays off. When a third is nonzero, the two representations cost about the same memory; if the matrix is denser, the triple representation takes more space and is not preferred.

Example 5.4

For the matrix in Figure 5.7: t = 8; the two-dimensional array takes 36 integers and the triple table takes 3 · 9 = 27. The triple representation wins. The threshold is 3(t + 1) < 36, that is, t ≤ 10; at t = 11 the two representations tie at 36 integers each.

In a 5 × 5 matrix the array takes 25 integers. The condition 3(t + 1) > 25 holds for t ≥ 8: at t = 7 the triples take 24 integers, at t = 8 they take 27. With eight or more nonzero entries the triple representation takes more space.

This calculation compares only memory. For time the picture is different: in the triple representation an entry cannot be reached directly like a[i][j]. To read the entry (i, j), the table must be searched. Thanks to sortedness, binary search finds it in O(log t), but that is still not O(1). A sparse representation suits operations that walk through all nonzero entries rather than reading single entries. Transpose and multiplication are such operations.

Common mistake

Mistaking M[0] for a nonzero entry. Loops start at j = 1 and end with the condition j <= M[0].value. A loop that starts at j = 0 processes the header too: the header (6, 6, 8) of the 6 × 6 matrix would be read as “the value at row 6, column 6 is 8”. There is no such cell in the matrix, and it can lead to writing outside the bounds of the array.

5.7Transposing

The transpose is one of the simplest matrix operations, and it shows both the strength and the trap of the sparse representation.

5.7.1The transpose and the ordering problem

Definition 5.4

The transpose M′ of a matrix M is the matrix whose rows are the columns of M: M′[j][i] = M[i][j] for every i, j. The transpose of a matrix of size rows × cols has size cols × rows.

M1304→M′1034
Figure 5.9: A 2 × 2 matrix and its transpose. The first row (1, 3) becomes the first column of the transpose.

On a two-dimensional array the transpose is two nested loops: t[j][i] = m[i][j]. With triples, the first idea that comes to mind is to swap the row and col fields of every triple. This gives the right position of each entry, but breaks the order. In the matrix of Figure 5.7, M[1] = (0, 0, 15), M[2] = (0, 3, 22) and M[3] = (0, 5, −15). Swapping the fields gives (0, 0, 15), (3, 0, 22), (5, 0, −15). The next one, M[4] = (1, 1, 11), becomes (1, 1, 11). The result table runs 0, 3, 5, 1, … and is no longer in row order. Every algorithm that relies on row order, such as multiplication and binary search, would work incorrectly with this table.

There are two crude ways to restore the order. The fields are swapped and the table is sorted afterwards; or each triple is inserted at the right place in the result table and the following triples are shifted by one position. Both are expensive. The course instructor puts it this way: if shifting and moving are used, the data structure is not being given its due. A better solution comes from the definition of the transpose. The rows of the transpose are the columns of M. So if M is scanned column by column, the rows of the transpose are produced in order.

5.7.2transpose(): scanning column by column

void transpose(term M[], term T[]) {
  int n = M[0].value, i, j, cur;
  T[0].row = M[0].col;  T[0].col = M[0].row;
  T[0].value = n;
  if (n > 0) {
    cur = 1;                       /* next slot in T */
    for (i = 0; i < M[0].col; i++)     /* each column */
      for (j = 1; j <= n; j++)         /* each term */
        if (M[j].col == i) {
          T[cur].row = M[j].col; T[cur].col = M[j].row;
          T[cur].value = M[j].value;  cur++;
        }
  }
}

The function first writes the header: the number of rows of the transpose is the number of columns of M, and its number of columns is the number of rows of M. The number of nonzero entries does not change. If the matrix is not empty, two nested loops run. The outer loop makes one round for each column i of M. The inner loop scans all triples of M and writes those whose column is i into T. cur is the next free slot in T.

Why the result comes out sorted rests on two observations. First, since the outer loop walks through the columns in increasing order, the entries of column 0 of M are written to T first, then those of column 1. These are rows 0 and 1 of T; row order is satisfied. Second, since the entries of the same column stand in row order in M, the inner loop finds them in row order. In T these row numbers become column numbers; so the column order within the same row is satisfied as well.

Note that the inner loop starts at j = 1. If it started at j = 0, the header M[0] would be scanned too. M[0].col is the number of columns and never equals any value of i, because i goes up to at most one less than the number of columns. The result would therefore not be corrupted, but an unnecessary comparison would be made for every column. The correct start is j = 1.

5.7.3Code trace and analysis

A small matrix is used for the trace: M, of size 3 × 4 with four nonzero entries. The nonzero entries are M[1] = (0, 0, 7), M[2] = (0, 3, 3), M[3] = (1, 1, 4) and M[4] = (2, 0, 2). The columns of the triples are 0, 3, 1, 0 respectively.

rowcolvalueM[0]344M[1]007M[2]033M[3]114M[4]202rowcolvalueT[0]434T[1]T[2]T[3]T[4]0071020331040022000M (3×4)
Figure 5.10: The start of transpose. On the left the triples of M, in the middle T with its header written, on the right the two-dimensional view of M.
Table 5.7: Trace of transpose(M, T), summarized per column.
iComparison with M[1..4].colMatching jWrittencur (after)
—header—T[0] = (4, 3, 4)1
00 = 0, 3 ≠ 0, 1 ≠ 0, 0 = 01, 4T[1] = (0, 0, 7), T[2] = (0, 2, 2)3
10 ≠ 1, 3 ≠ 1, 1 = 1, 0 ≠ 13T[3] = (1, 1, 4)4
20 ≠ 2, 3 ≠ 2, 1 ≠ 2, 0 ≠ 2——4
30 ≠ 3, 3 = 3, 1 ≠ 3, 0 ≠ 32T[4] = (3, 0, 3)5

The outer loop runs four rounds and the inner loop four steps per round: 4 · 4 = 16 comparisons are made. Only four of them match; twelve are wasted. Column 2 has no nonzero entry at all, yet all triples are still scanned. The result T comes out sorted by row automatically: (0, 0, 7), (0, 2, 2), (1, 1, 4), (3, 0, 3).

rowcolvalueM[0]344M[1]007M[2]033M[3]114M[4]202rowcolvalueT[0]434T[1]007T[2]022T[3]114T[4]3030071020331040022000M (3×4)
Figure 5.11: T when transpose finishes. The transpose has size 4 × 3; the triples are in row order, then column order.

The function has also been applied to the 6 × 6 matrix of Figure 5.7. The result table is (0, 0, 15), (0, 4, 91), (1, 1, 11), (2, 1, 3), (2, 5, 28), (3, 0, 22), (3, 2, −6), (5, 0, −15) (Figure 5.12). Here 6 · 8 = 48 comparisons are made.

rowcolvalueT[0]668T[1]0015T[2]0491T[3]1111T[4]213T[5]2528T[6]3022T[7]32-6T[8]50-15
Figure 5.12: The transpose T of the 6 × 6 example matrix. The 91 of M (row 4, column 0) sits at row 0, column 4 in the transpose.

The complexity can be read off the nested loops. The outer loop runs cols times and the inner loop terms times; the inner body does constant work. The time is O(cols · terms). This cost depends on how sparse the matrix is. If the matrix is full, terms = rows · cols and the cost rises to O(cols2 · rows). On a two-dimensional array the transpose takes O(rows · cols). On a full matrix, transpose is slower by a factor of cols.

So the triple representation has gained in memory but lost in time. This trade is meaningful only when terms ≪ rows · cols. The source of the problem is clear: the same array M is rescanned from start to end for every column. If it were known beforehand where each term will go in T, M could be scanned once and every term placed directly. For example, suppose it is known that row 0 of the transpose will have 2 entries and row 1 will have 3. Row 0 starts at T[1], row 1 at T[3], row 2 at T[6]. The fast transpose computes this information in advance.

5.7.4fast_transpose(): count first, then place

Definition 5.5

The fast transpose is a method that transposes a sparse matrix in two passes. The first pass counts the nonzero entries in each column and computes the position in the table at which each row of the transpose will start. The second pass writes each triple directly to that position.

void fast_transpose(term M[], term T[]) {
  int i, j, nc = M[0].col, nt = M[0].value;
  int row_terms[MAX_COL], start_pos[MAX_COL];
  T[0].row = nc;  T[0].col = M[0].row;  T[0].value = nt;
  if (nt <= 0) return;                    /* empty matrix */
  for (i = 0; i < nc; i++) row_terms[i] = 0;
  for (i = 1; i <= nt; i++) row_terms[M[i].col]++;
  start_pos[0] = 1;
  for (i = 1; i < nc; i++)
    start_pos[i] = start_pos[i-1] + row_terms[i-1];
  for (i = 1; i <= nt; i++) {
    j = start_pos[M[i].col]++;       /* take the slot, advance */
    T[j].row = M[i].col;  T[j].col = M[i].row;
    T[j].value = M[i].value;
  }
}

The function uses two helper arrays. row_terms[i] is the number of entries in row i of the transpose, that is, in column i of M. start_pos[i] is the first position of row i of the transpose in T. The code has four loops:

  1. row_terms is zeroed. In C, local arrays are not initialized; the values in them are indeterminate. If the zeroing is skipped, the counters start from random values.
  2. Counting. For each triple of M, the counter of its own column is incremented: row_terms[M[i].col]++.
  3. Starting positions. Row 0 starts at T[1]. Each row is found by adding the number of entries of the previous row to the start of the previous row: start_pos[i] = start_pos[i-1] + row_terms[i-1]. This is a prefix sum: start_pos[i] is 1 plus the sum of all counters from 0 to i − 1.
  4. Placement. M is scanned once from start to end. Each triple is written where the start_pos value of its column points, and this value is incremented. The next triple from the same column falls in the next position.

The line j = start_pos[M[i].col]++; of the fourth loop is a dense expression. First M[i].col is read; this is the index into the array. The postfix ++ operator first gives the old value of start_pos[M[i].col] to j, then increments the array cell. If the prefix form ++start_pos[M[i].col] were written, the increment would happen first and j would be one too large: the first triple would be written to T[2], and the triple belonging to the last position would overflow the array. The instructor's warning is about this line: a programmer must know well the operator precedence of the language they write in. Here the square brackets and the . operator are applied before the postfix ++; what is incremented is that cell of the start_pos array, not M[i].col.

Why is the order of the triples preserved? Since M is scanned in row order, the entries of the same column arrive in row order. Each is written to the next free position of its own row. Within each row of the transpose, the entries are in increasing order of the row numbers in M, that is, of the column numbers in the transpose. The order of the rows themselves comes from the start_pos values being increasing.

5.7.5Code trace: the two phases

The same 3 × 4 matrix is used. The first phase counts and finds the starting positions (Table 5.8).

Table 5.8: fast_transpose first phase: counting and prefix sum.
StepActionrow_termsstart_pos
1header: T[0] = (4, 3, 4); counters zeroed[0, 0, 0, 0]—
2M[1] is in column 0[1, 0, 0, 0]—
3M[2] is in column 3[1, 0, 0, 1]—
4M[3] is in column 1[1, 1, 0, 1]—
5M[4] is in column 0[2, 1, 0, 1]—
6start_pos[0] = 1[2, 1, 0, 1][1, ·, ·, ·]
7start_pos[1] = 1 + 2 = 3[2, 1, 0, 1][1, 3, ·, ·]
8start_pos[2] = 3 + 1 = 4[2, 1, 0, 1][1, 3, 4, ·]
9start_pos[3] = 4 + 0 = 4[2, 1, 0, 1][1, 3, 4, 4]

The equality in the last step stands out: start_pos[2] and start_pos[3] are both 4. Since column 2 has no entries, row 2 of the transpose is empty and row 3 starts where row 2 would have started. An empty row shows up as two consecutive equal starting positions.

rowcolvalueM[0]344M[1]007M[2]033M[3]114M[4]202row_terms2101start_pos1344col 0col 1col 2col 3
Figure 5.13: The end of the first phase: row_terms = [2, 1, 0, 1], start_pos = [1, 3, 4, 4].

The second phase scans M once (Table 5.9).

Table 5.9: fast_transpose second phase: placement.
iM[i]j = start_pos[M[i].col]++Writtenstart_pos (after)
1(0, 0, 7)start_pos[0]: j = 1T[1] = (0, 0, 7)[2, 3, 4, 4]
2(0, 3, 3)start_pos[3]: j = 4T[4] = (3, 0, 3)[2, 3, 4, 5]
3(1, 1, 4)start_pos[1]: j = 3T[3] = (1, 1, 4)[2, 4, 4, 5]
4(2, 0, 2)start_pos[0]: j = 2T[2] = (0, 2, 2)[3, 4, 4, 5]

The triples are written to T out of order: first T[1], then T[4], T[3] and T[2]. But each goes to the right place, and in the end T is the same as the table produced by transpose. When the phase ends, start_pos[i] points to the position after the last entry of row i; that is, start_pos[i] is now the start of row i + 1. Because column 2 is empty, start_pos[2] has never changed.

rowcolvalueM[0]344M[1]007M[2]033M[3]114M[4]202row_terms2101start_pos2345col 0col 1col 2col 3rowcolvalueT[0]434T[1]007T[2]T[3]T[4]303
Figure 5.14: The second step of the second phase: M[2] = (0, 3, 3) has been written directly to T[4]; T[2] and T[3] are still empty.

On the 6 × 6 example matrix the first phase produces row_terms = [2, 1, 2, 2, 0, 1] and start_pos = [1, 3, 4, 6, 8, 8]. Since column 4 is empty, start_pos[4] and start_pos[5] are equal. These values have been verified by a program.

5.7.6Analysis, the one-array version and measurement

The four loops of fast_transpose run cols, terms, cols − 1 and terms rounds respectively. None is nested. Together with the constant number of operations outside the loops, the total work is

2 · terms + 2 · cols + constant = O(cols + terms)

On a full matrix terms = rows · cols, so the cost is O(rows · cols): the same order as the transpose of a two-dimensional array. On a sparse matrix the cost is proportional to the number of nonzero entries. The price is two helper arrays of size cols: O(cols) extra memory.

Theorem 5.2 (Cost of the two transposes)

For a sparse matrix of size rows × cols with t nonzero entries, transpose runs in Θ(cols · t) time and fast_transpose in Θ(cols + t) time. Both produce a transpose in the correct order.

The fast transpose can also be written with a single helper array. This recalls the instructor's question: it was said that fast transpose can be done with one array; here it is. Once the counting is finished, the counters are no longer needed; the same array is converted in place into the starting positions:

/* convert row_terms in place into start_pos */
for (i = 0, pos = 1; i < nc; i++) {
  int c = row_terms[i];  /* terms in this column */
  row_terms[i] = pos;  /* now a start position */
  pos += c;
}
for (i = 1; i <= nt; i++) {
  j = row_terms[M[i].col]++;
  T[j].row = M[i].col;  T[j].col = M[i].row;
  T[j].value = M[i].value;
}

In this code row_terms is the array of counts, as in the earlier version. The first loop reads each counter, writes the starting position of that row in its place, and advances pos by the counter. If the old value of the counter is not saved in the local variable c, the overwritten value is read and pos advances wrongly. The second loop is the same as the placement loop of the earlier version. This form was compiled as a complete function in the test program of these notes and was seen to give the same result as the version with two helper arrays.

The one-array version is counting sort itself. Counting sort sorts items whose keys come from a small range: first it counts how many items there are of each key, finds the starting position of each key with a prefix sum, then puts the items in their places one by one. In the fast transpose, the key is the column number. Because the relative order of items with the same key in the input is preserved, the sort is stable and the row order is not disturbed.

The difference is striking on large matrices. Table 5.10 gives measurements of the two functions of the slides, compiled with -O2 after only enlarging the constants MAX_TERMS and MAX_COL. Each row has ten nonzero entries. The times vary by machine; what matters is the growth rate.

Table 5.10: Transpose times (milliseconds; they vary by machine).
SizeNonzero entriestransposefast_transpose
1000 × 100010,000≈ 4≈ 0.04
2000 × 200020,000≈ 14≈ 0.08
4000 × 400040,000≈ 60≈ 0.26
8000 × 800080,000≈ 254≈ 0.36

When the size doubles, both the number of columns and the number of nonzero entries double. Since the time of transpose is proportional to cols · t, it roughly quadruples: 4, 14, 60, 254. The time of fast_transpose is proportional to cols + t and roughly doubles. On the largest matrix the difference between the two methods is close to a factor of seven hundred. The small times are near the limit of measurement precision; that is why the fast transpose was run fifty times and averaged.

Common mistake

Swapping only row and col in the transpose and forgetting to sort the table. The result contains the right entries but is not in row order. A multiplication done with this table gives a wrong result, because it assumes that the entries of the same row are consecutive. The bug may not show up on small examples: a one-row or diagonal matrix stays sorted even when the fields are simply swapped.

5.8Sparse matrix multiplication

Matrix multiplication is the operation where the sparse representation helps most and where the code must be written most carefully. The code in this section is a simplified adaptation of Horowitz's mmult program.

5.8.1Row times column

Let A be an m × n matrix and B an n × p matrix. Their product D = A · B has size m × p, and each of its entries is given by

dij = Σk=0n−1 aik · bkj

Row i of A and column j of B are multiplied entry by entry and summed. In sparse matrices most terms of this sum are zero. The product aik · bkj is nonzero only if both entries are nonzero. So only the pairs of entries that are nonzero for the same value of k need to be multiplied.

The product of two sparse matrices need not be sparse. In each of the two matrices of Figure 5.15, three of the nine cells are nonzero, yet all nine cells of their product are nonzero. All nonzero entries of A are in column 0, and all nonzero entries of B are in row 0; every pair (i, j) meets at k = 0.

A100100100·B111000000=D111111111
Figure 5.15: The product of two sparse matrices can be full. Three of the nine cells are nonzero in A and in B; all nine cells of D are 1.

In the triple representation, row i of A is consecutive. But column j of B is scattered over the table: at most one entry from each row, at different places in the table. Summing one column requires scanning the whole table. The solution is to transpose B first. In BT, obtained with fast_transpose, the columns of B become consecutive rows. Then each row of A and each row of BT are merged by their col fields and multiplied. The column of an entry in row i of A is k; the column of an entry in row j of BT is its row in B, which is again k. The entries of the two rows with the same col value are the pairs to be multiplied.

Which matrix is transposed matters. It would be wrong to say “the first matrix is transposed first”. In Horowitz's mmult, and logically, the matrix that is transposed is the second one, B. The rows of A are already consecutive; the problem lies in the columns of B.

5.8.2Helpers: row_end(), dot(), store()

The product is written with three small helpers. The first two are these:

/* where the row of the term at s ends */
int row_end(term t[], int s) {
  int e = s;
  while (e <= t[0].value &&
         t[e].row == t[s].row) e++;
  return e;
}
/* row a[x..ex) times row b[y..ey) */
int dot(term a[], int x, int ex,
        term b[], int y, int ey) {
  int sum = 0;
  while (x < ex && y < ey)
    if (a[x].col < b[y].col) x++;
    else if (a[x].col > b[y].col) y++;
    else sum += a[x++].value * b[y++].value;
  return sum;
}

row_end(t, s) finds where the triples in the same row as the triple t[s] end. e starts at s and advances until the row number changes or the table ends. The returned e is the index one past the last entry of the row. The row is the half-open range [s, e): s included, e excluded. This is the usual form of array loops in C; an empty range appears as s = e and the length of the range is e − s. The order in the condition matters: e <= t[0].value is tested first. Because the && operator short-circuits, t[e] is never read with an e past the end of the table.

dot computes the dot product of the row [x, ex) of a and the row [y, ey) of b. This is a two-pointer merge like padd. The entries of both rows are sorted by column. If the columns differ, the pointer with the smaller column advances, because that column has no counterpart in the other row. If the columns are equal, the two values are multiplied and added to the sum, and both pointers advance. The loop stops when one of the rows is exhausted; the remaining entries cannot have a counterpart. The cost is proportional to the sum of the numbers of entries of the two rows.

The third helper writes the result:

void store(term d[], int *nd,
           int r, int c, int s) {
  if (s == 0) return;
  if (++*nd >= MAX_TERMS) {
    fprintf(stderr, "Too many terms\n");
    exit(1);
  }
  d[*nd].row = r;
  d[*nd].col = c;
  d[*nd].value = s;
}

store writes nothing if the sum is 0; zero entries do not enter the sparse table. Otherwise the counter is incremented first and then the triple is written. In the expression ++*nd, the prefix ++ and * have the same precedence and bind right to left: it means ++(*nd). First the counter that nd points to is incremented, then the new value is compared with the limit. The result exceeding MAX_TERMS is an error. Since there is no guarantee that the product stays sparse, this check is not decoration.

5.8.3smult() and a code trace

void smult(term a[], term bt[], term d[]) {
  int ra, ea, rb, eb, nd = 0;
  for (ra = 1; ra <= a[0].value; ra = ea) {
    ea = row_end(a, ra);       /* row of A [ra,ea) */
    for (rb = 1; rb <= bt[0].value; rb = eb) {
      eb = row_end(bt, rb);    /* column of B [rb,eb) */
      store(d, &nd, a[ra].row, bt[rb].row,
            dot(a, ra, ea, bt, rb, eb));
    }
  }
  d[0].row = a[0].row;  d[0].col = bt[0].row;
  d[0].value = nd;
}

The function takes A and bt, the transpose of B. The outer loop walks through the rows of A: ra is the first triple of the row and ea = row_end(a, ra) is the end of the row. The next round starts with ra = ea, that is, from the next row. The inner loop walks the same way through the rows of bt, that is, the columns of B. For each pair of rows, dot computes the dot product and store writes it to the result if it is not zero. The row of the result triple is a[ra].row and its column is bt[rb].row: the row number in BT is the column number in B.

The result triples come out in the right order automatically. The outer loop walks the rows of A and the inner loop the columns of B in increasing order. This is row-major order itself. The header is written last, because the number of nonzero entries is known only when the loops are finished. Empty rows and empty columns are never visited; the loops walk only through the rows that appear in the table.

The trace uses A = [[1, 0, 2], [0, 3, 0]] (2 × 3) and B = [[4, 0], [0, 5], [6, 0]] (3 × 2). The tables are: a = (2, 3, 3) | (0, 0, 1), (0, 2, 2), (1, 1, 3). The transpose of B is 2 × 3: bt = (2, 3, 3) | (0, 0, 4), (0, 2, 6), (1, 1, 5).

Table 5.11: Trace of smult(a, bt, d).
StepRow of AColumn of Bdotstorend
10: a[1..2] (columns 0, 2)0: bt[1..2] (columns 0, 2)1·4 + 2·6 = 16d[1] = (0, 0, 16)1
20: a[1..2]1: bt[3..3] (column 1)no common column: 0not stored1
31: a[3..3] (column 1)0: bt[1..2]no common column: 0not stored1
41: a[3..3]1: bt[3..3]3·5 = 15d[2] = (1, 1, 15)2
5header: d[0] = (2, 2, 2)2

In the first step dot merges the columns {0, 2} of row 0 of A with the rows {0, 2} of column 0 of B. There are two matches: 1 · 4 at k = 0 and 2 · 6 at k = 2. The sum is 16. In the second step the columns of A are {0, 2} and the rows of column 1 of B are {1}; there is no common value, and since the sum is 0 nothing is written. The result is D = [[16, 0], [0, 15]].

rowcolvaluea[0]233a[1]001a[2]022a[3]113rowcolvaluebt[0]233bt[1]004bt[2]026bt[3]115rowcolvalued[0]222d[1]0016d[2]1115A (2×3)Bᵀ (B: 3×2)D = A·B (2×2)
Figure 5.16: When smult finishes: the triple tables of A, BT and the result D. The header of D is written last: 2 × 2, two nonzero entries.

The correctness of the code has been tested beyond small examples. The test program generated 3,000 pairs of matrices with sizes chosen at random between 1 and 6 and about a quarter of the entries nonzero. The result of fast_transpose + smult for each pair came out equal to the classical product computed with three nested loops. In the same test, transpose, fast_transpose and the one-array version also gave the same transpose for every matrix. The example in Figure 5.15 shows that the product can produce a full table of nine entries.

5.8.4Complexity

Let the number of nonzero entries of A be tA and that of B be tB. The cost has three parts:

  • Transpose. fast_transpose(B): O(colsB + tB).
  • Walking through BT. For each row of A, bt is walked from start to end; the calls to row_end and the steps of dot on the bt side add up to O(tB) per row. For at most rowsA rows of A: Σi tB = rowsA · tB.
  • Walking through the rows of A. For each pair (i, j), dot also walks through row i of A. j takes at most colsB values; for each j the rows of A total tA entries: Σj tA = colsB · tA.
Theorem 5.3 (Cost of sparse multiplication)

The product of matrices A (tA nonzero entries) and B (tB nonzero entries) given in triple representation is computed, transpose included, in O(colsB · tA + rowsA · tB) time.

The cost O(colsB + tB) of the transpose stays inside this sum. The classical product takes O(rowsA · colsA · colsB): three nested loops. If the matrices are full, tA = rowsA · colsA and tB = colsA · colsB, and the sparse version also rises to the order of O(rowsA · colsA · colsB). The order is the same, but the constant is larger: three fields are read for every entry and comparisons are made.

The sparse version pays off when tA and tB are a small fraction of the matrix sizes. For example, let two matrices of size 1000 × 1000 have five nonzero entries in each row: tA = tB = 5000. The classical product makes 109 multiplications. The bound of the sparse product is 1000 · 5000 + 1000 · 5000 = 107; a hundred times fewer. But there is no guarantee that the result D will be sparse. A full result as in Figure 5.15 can exceed MAX_TERMS; this is why the check in store exists.

Common mistake

Transposing A in the product. The rows of A are already consecutive; transposing would scatter them and does not solve the problem. The matrix that must be transposed is B, whose columns are scattered. Another mistake is to assume that the result stays sparse and allocate a small result table.

5.9Other representations

The triple representation is instructive and simple, but it is not the only choice. The format most used in scientific computing is compressed sparse row storage. In applications that need frequent insertion and deletion, a linked representation comes to the fore.

5.9.1Compressed sparse row (CSR)

Definition 5.6

Compressed sparse row (CSR) storage keeps a sparse matrix in three arrays. val holds the values of the nonzero entries and col_ind holds their column numbers, both in row-major order; both have length t. The array row_ptr has length rows + 1: row_ptr[i] is the index in val of the first entry of row i, and row_ptr[rows] = t.

val0151222-15311435-6691728col_ind03512302row_ptr0356678Row 1: val[3..4]
Figure 5.17: The CSR representation of the 6 × 6 example matrix. Row 1 is val[3..4]; row 3, which is empty, shows up as two consecutive equal row_ptr values (6, 6).

In the triple representation the row number of every entry is written out separately. Since entries of the same row are consecutive, this information is repeated needlessly. CSR drops the row numbers and keeps where each row starts. The entries of row i are in the range val[row_ptr[i] .. row_ptr[i+1] − 1]; the length of the range is row_ptr[i+1] − row_ptr[i].

In the 6 × 6 example, row_ptr = [0, 3, 5, 6, 6, 7, 8]. Row 0 is val[0..2]: 15, 22, −15. Row 3 has no entries; row_ptr[3] = row_ptr[4] = 6. Memory: val 8, col_ind 8, row_ptr 7 integers, 23 in total. The triple representation took 27 integers. The difference becomes noticeable in large matrices: triples take 3t integers, CSR takes 2t + rows + 1.

The most important use of CSR is matrix–vector multiplication: y = M · x. Iterative equation solvers do this operation thousands of times.

/* y = M * x  (matrix-vector product) */
for (i = 0; i < rows; i++) {
  y[i] = 0;
  for (k = row_ptr[i]; k < row_ptr[i+1]; k++)
    y[i] += val[k] * x[col_ind[k]];
}

The outer loop walks through the rows. The inner loop walks through the nonzero entries of row i: the value of each entry is multiplied by the vector entry in the same column and added to y[i]. The expression x[col_ind[k]] is an indirect access: first the column number is read, then that position of the vector. The outer loop runs rows rounds and the inner loops t rounds in total. The cost is O(rows + t). When the example matrix is multiplied by x = (1, 2, 3, 4, 5, 6), the result is y = (13, 31, −24, 0, 91, 84); the first entry is 15 · 1 + 22 · 4 − 15 · 6 = 13.

row_ptr is the same idea as start_pos in fast_transpose: the starting position of each row is the prefix sum of the entry counts of the earlier rows. Building CSR from a triple table is also done by counting: the entries of each row are counted and the prefix sum is taken. The column-major counterpart is CSC (compressed sparse column): columns are compressed instead of rows. The CSR representation of a matrix consists of the same arrays as the CSC representation of its transpose.

5.9.2The linked sparse matrix

The triple array and CSR are very good for a fixed matrix, but struggle when the matrix changes. Inserting or deleting an entry requires shifting the sorted array and takes O(t). The triple array also has the limit MAX_TERMS.

In the linked representation every nonzero entry is a node. A node holds the row, the column, the value and two links: to the next entry in the same row and to the next entry in the same column. The nodes in the same row form a circular linked list; so do those in the same column. Each row and each column has a header node. The header nodes are also linked among themselves, so the whole matrix can be traversed from a single entry point. Horowitz builds this structure in detail in the linked lists chapter of his book.

The gain of this representation is flexibility. Once the position has been found, inserting or deleting an entry takes a few link changes, in O(1) time. Traversal by both row and column is easy: walking along a row or a column means walking along the corresponding circular list. So multiplication does not need a transpose. The price is the extra memory of two pointers per entry; on a 64-bit system 16 bytes are added to the 12 bytes of three integers.

The linked implementation of a sparse matrix is a direct application of linked lists. Linking a node into two lists at once, updating the links of both lists consistently in insertion and deletion, and freeing all nodes without a leak are a good test of linked-list skill. The course instructor stresses in particular that this work must be each student's own effort: if two homework papers are laid on top of each other and held up to the light, they should not look the same.

5.10Complexity summary

Table 5.12 brings together the costs of the operations studied in these notes.

Table 5.12: Costs of polynomial and sparse matrix operations.
OperationTimeRemark
Addition with coefficient arraysO(d)d: degree; wasteful for sparse polynomials
padd (n, m terms)Θ(n + m)sorted terms + merging
pmult (array, repeated padd)O(n2m)smaller polynomial outside: O(min2 · max); leftovers pile up
pmult_list (linked list)O(n2m) worst casethe search is shortened by anchor; depends on the arrangement in measurements
transposeO(cols · terms)on a full matrix O(cols2 · rows)
fast_transposeO(cols + terms)O(cols) extra memory; counting sort
Sparse product (smult / mmult)O(colsB · tA + rowsA · tB)BT first
M · x with CSRO(rows + terms)row-start array

The table has a common lesson. All the fast algorithms rest on sortedness and merging: padd merges two sorted term arrays, dot merges two sorted rows; fast_transpose produces a sorted table with counting sort. The memory gain of the sparse representation turns into a time gain only if this order is preserved.

5.11Common mistakes

The mistakes met most often in the code of these notes are the following:

  1. Keeping the terms unsorted but still writing padd with two pointers. Merging is correct only on sorted input. On unsorted input, two terms with the same exponent may never see each other and remain as two separate terms in the result.
  2. Appending a term whose sum is 0 to the result, or not deleting it from the list. The if (c) check in padd and the call to delete_next in place exist for this reason. The memory of a deleted node must be returned with free.
  3. Truncating a float coefficient with an int parameter in attach; not checking for overflow of avail. The truncation happens without a compiler warning. Without the overflow check, memory past the end of the array is corrupted.
  4. Swapping only the row and col fields in the transpose and forgetting to sort; mistaking the header M[0] for a term. An unsorted transpose breaks operations that rely on order, such as multiplication. Loops must start at 1.
  5. Confusing prefix and postfix in start_pos[M[i].col]++. The postfix form uses the old value and then increments; with the prefix form every triple shifts by one position and the triple belonging to the last position is written outside the table.
  6. Transposing A in sparse multiplication; assuming the result stays sparse. The matrix to transpose is B. The result can be full; the limit of the result table must be checked.
  7. Mixing up the order of deletion in a linked list. If the link is updated without saving the node's address, memory leaks; if the node is freed before the link is updated, a dangling pointer remains.
  8. Not zeroing local counter arrays. Local arrays like row_terms start with indeterminate values in C; they must be zeroed before the counting loop.

5.12Summary

  • The representation matters. The coefficient array is simple and fast for dense, low-degree polynomials, but for sparse polynomials it spends memory and time on zeros. The term array stores only the nonzero terms, sorted from the largest exponent to the smallest.
  • Sortedness and merging. padd adds two sorted term arrays by walking through them with two pointers, in Θ(n + m) time. A term whose sum is 0 is not written to the result. In the shared array P the space of leftovers is not reclaimed; compaction or a linked list is needed.
  • Multiplication on arrays. pmult multiplies by each term in turn and adds the result with padd: O(n2m). The smaller polynomial should go in the outer loop. Many polynomials are merged with a priority queue or two at a time.
  • The linked list. It is flexible when the number of terms is unknown. pmult_list places the products in a sorted list, combines equal exponents, deletes terms that become zero and returns their memory. The variable anchor shortens the search; the worst case is still Θ(n2m).
  • Triples. A sparse matrix is stored as ⟨row, column, value⟩ triples with the header M[0]. The triples are in row order, then column order. The representation pays off when 3(t + 1) < rows · cols, roughly when less than a third of the matrix is nonzero.
  • Transpose. Swapping the fields breaks the order. transpose scans column by column in O(cols · t); fast_transpose counts first and then places, in O(cols + t) time. The fast transpose is counting sort with the column number as the key.
  • Multiplication. First B is transposed; then each row of A is merged and multiplied with each row of BT: O(colsB · tA + rowsA · tB). There is no guarantee that the result stays sparse.
  • Other representations. CSR keeps row starts instead of row numbers and performs matrix–vector multiplication in O(rows + t); row_ptr is the same prefix-sum idea as start_pos. The linked sparse matrix brings insertion and deletion down to O(1), but spends two pointers per entry.

5.13Key terms

  • polynomial
  • abstract data type
  • merge
  • priority queue
  • memory leak
  • dangling pointer
  • sparse matrix
  • triple
  • row-major order
  • transpose
  • fast transpose
  • counting sort
  • key
  • compressed sparse row
  • circular linked list
  • header node

5.14Test Yourself

  1. For A = 5x6 − 2x3 + 4 and B = 2x6 + 2x3 + x − 4, how many rounds does the main loop of padd run, how many calls to attach are made, and what is the result?

    Answer

    The loop runs four rounds: (6, 6) equal, 5 + 2 = 7 is written; (3, 3) equal, −2 + 2 = 0 is not written; (0, 1) B is larger, x is written; (0, 0) equal, 4 − 4 = 0 is not written. Both polynomials are exhausted at the same time. Two calls to attach are made and the result is 7x6 + x.

  2. With avail = 5, A = x2 + 1 and B = x2 + x + 1 are multiplied with pmult. What is the result and what is avail when it finishes? How many of the positions used hold the result?

    Answer

    The result is x4 + x3 + 2x2 + x + 1 (5 terms). In the first round 3 temporary terms are written and padd copies them to the empty partial result (3 more terms). In the second round 3 temporary terms and the new partial result of 5 terms are written. In total 3 + 3 + 3 + 5 = 14 positions are used; avail becomes 19. Of the 14 positions only 5 are the result.

  3. In the product (x2 + x)(x − 1), which term does pmult_list delete? What is the result?

    Answer

    In the round p = x2, x3 and −x2 are added. In the round p = x, x · x = +x2 arrives; the coefficient becomes −1 + 1 = 0 and the x2 node is deleted. The last product −x is appended at the end. The result is x3 − x.

  4. Why is the first node of the result list in pmult_list never deleted? Which helper's restriction does this property make harmless?

    Answer

    The first node is the product of the terms with the largest exponents of the two polynomials. Its exponent is larger than that of all other products and no other pair of terms can produce the same exponent; its coefficient is never updated and cannot become 0. delete_next can delete only the node after the given node, not the first node. Since the first node is never deleted, this restriction causes no problem.

  5. In a 100 × 100 matrix, up to how many nonzero entries does the triple representation take less space than the two-dimensional array?

    Answer

    The condition is 3(t + 1) < 10,000. At t = 3332 the triples take 3 · 3333 = 9999 integers, which is smaller; at t = 3333 they take 10,002 integers. The limit is t ≤ 3332, about a third of the matrix.

  6. The nonzero entries of a 4 × 5 matrix are (0, 2, 1), (1, 0, 3), (1, 2, −1), (2, 4, 6), (3, 2, 2). What are the row_terms and start_pos arrays of fast_transpose? In what order are the triples of the transpose written? How many comparisons does transpose make?

    Answer

    The columns are 2, 0, 2, 4, 2: row_terms = [1, 0, 3, 0, 1], start_pos = [1, 2, 2, 5, 5]. The transpose is (0, 1, 3), (2, 0, 1), (2, 1, −1), (2, 3, 2), (4, 2, 6). Rows 1 and 3 are empty; that is why start_pos[1] = start_pos[2] and start_pos[3] = start_pos[4]. transpose makes 5 · 5 = 25 comparisons.

  7. What is row_ptr in the CSR representation of the same 4 × 5 matrix? How many integers do the three arrays take in total?

    Answer

    row_ptr = [0, 1, 3, 4, 5]: row 0 has one entry, row 1 has two, rows 2 and 3 have one each. val and col_ind take five integers each and row_ptr takes five: 15 in total. The triple representation would take 3 · 6 = 18 integers.

  8. In fast_transpose, what happens on the 3 × 4 trace matrix if j = start_pos[M[i].col]++; is replaced with j = ++start_pos[M[i].col];?

    Answer

    The prefix form increments first and then yields the new value. The first triple (0, 0, 7) is written to T[2] instead of T[1]. Every triple goes one position past its correct place, and the last triple (2, 0, 2) lands in T[3] while (0, 3, 3) lands in T[5]. T[1] stays empty. T[5] is beyond T[4], the last valid position of a table with four nonzero entries; had the array been allocated for exactly five triples, the bound would be exceeded.

  9. Two matrices of size 1000 × 1000 each have 3,000 nonzero entries. What is the operation bound of the sparse product? What fraction of the number of multiplications of the classical product is it?

    Answer

    The bound of the sparse product is colsB · tA + rowsA · tB = 1000 · 3000 + 1000 · 3000 = 6 · 106. The classical product makes 10003 = 109 multiplications. The sparse method does about 167 times less work.

5.15Further reading

  • E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Sections 2.4–2.5 and 4.4, 4.7: the source of the padd, transpose, fast_transpose and mmult code of these notes; it gives the linked polynomial and the linked sparse matrix built with circular lists in detail.
  • Y. Saad, Iterative Methods for Sparse Linear Systems (2nd ed.), Section 3.4: describes CSR, CSC and other sparse storage formats together with their use in scientific computing.
  • T. H. Cormen et al., Introduction to Algorithms (3rd ed.), Section 8.2: gives counting sort, on which the fast transpose rests, with its stability and linear-time analysis.

5.16References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008 (Sections 2.4–2.5: polynomials and sparse matrices; 4.4 and 4.7: linked polynomials and sparse matrices).
  2. Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003 (Section 3.4: CSR/CSC formats).
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009 (Section 8.2: counting sort).

Related pages: Chapter 5 slides · © Sercan Külcü. All rights reserved.