100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Compressed Sparse Row Format Answer $10.49   Add to cart

Exam (elaborations)

Compressed Sparse Row Format Answer

 176 views  0 purchase
  • Course
  • Institution

Compressed Sparse Row Format This format tries to compress the sparse matrix further compared to COO format. Suppose you have the following coordinate representation of a sparse matrix where you sort by row index: rows = [0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5,...

[Show more]

Preview 2 out of 6  pages

  • January 18, 2022
  • 6
  • 2021/2022
  • Exam (elaborations)
  • Questions & answers
avatar-seller
Compressed Sparse Row Format

This format tries to compress the sparse matrix further compared to COO format. Suppose you have
the following coordinate representation of a sparse matrix where you sort by row index:


rows = [0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6]
cols = [1, 2, 4, 0, 2, 3, 0, 1, 3, 4, 1, 2, 5, 6, 0, 2, 5, 3, 4, 6, 3, 5]
values = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
If there are nnz nonzeroes, then this representation requires 3*nnz units of storage since it needs three
arrays, each of length nnz.
Observe that when we sort by row index, values are repeated wherever there is more than one
nonzero in a row. The idea behind CSR is to exploit this redundancy. From the sorted COO
representation, we keep the column indices and values as-is. Then, instead of storing every row
index, we just store the starting offset of each row in those two lists, which we'll refer to as the row
pointers, stored as the list rowptr, below:


cols = [1, 2, 4, 0, 2, 3, 0, 1, 3, 4, 1, 2, 5, 6, 0, 2, 5, 3, 4, 6, 3, 5]
values = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
rowptr = [0, 3, 6, 10, 14, 17, 20, 22]
If the sparse matrix has n rows, then the rowptr list has n+1 elements, where the last element
(rowptr[-1] == rowptr[n]) is nnz. (Why might you need this last element?)

Exercise 8 (3 points). Complete the function, coo2csr(coo_rows, coo_cols, coo_vals), below. The
inputs are three Python lists corresponding to a sparse matrix in COO format, like the example
illustrated above. Your function should return a triple, (csr_ptrs, csr_inds, csr_vals), corresponding to
the same matrix but stored in CSR format, again, like what is shown above, where csr_ptrs would be
the row pointers (rowptr), csr_inds would be the column indices (colind), and csr_vals would be the
values (values).

To help you out, we show how to calculate csr_inds and csr_vals. You need to figure out how to
compute csr_ptrs. The function is set up to return these three lists.
Although the test cell does not check it, in principle, your implementation should also work correctly
if a row has an empty row. In such cases, what should the CSR data structure look like?

Write code here

def coo2csr(coo_rows, coo_cols, coo_vals):
from operator import itemgetter
C = sorted(zip(coo_rows, coo_cols, coo_vals), key=itemgetter(0))
nnz = len(C)
assert nnz >= 1

csr_inds = [j for _, j, _ in C]
csr_vals = [a_ij for _, _, a_ij in C]

# Your task: Compute `csr_ptrs`
###

, ### YOUR CODE HERE




Testing codes

# Test cell 0: `create_csr_test` (1 point)

csr_ptrs, csr_inds, csr_vals = coo2csr(coo_rows, coo_cols, coo_vals)

assert type(csr_ptrs) is list, "`csr_ptrs` is not a list."
assert type(csr_inds) is list, "`csr_inds` is not a list."
assert type(csr_vals) is list, "`csr_vals` is not a list."

assert len(csr_ptrs) == (num_verts + 1), "`csr_ptrs` has {} values instead of {}".format(len(csr_ptrs),
num_verts+1)
assert len(csr_inds) == num_edges, "`csr_inds` has {} values instead of {}".format(len(csr_inds),
num_edges)
assert len(csr_vals) == num_edges, "`csr_vals` has {} values instead of {}".format(len(csr_vals),
num_edges)
assert csr_ptrs[num_verts] == num_edges, "`csr_ptrs[{}]` == {} instead of {}".format(num_verts,
csr_ptrs[num_verts], num_edges)

# Check some random entries
for i in sample(range(num_verts), 10000):
assert i in G
a, b = csr_ptrs[i], csr_ptrs[i+1]
msg_prefix = "Row {} should have these nonzeros: {}".format(i, G[i])
assert (b-a) == len(G[i]), "{}, which is {} nonzeros; instead, it has just {}.".format(msg_prefix,
len(G[i]), b-a)
assert all([(j in G[i]) for j in csr_inds[a:b]]), "{}. However, it may have missing or incorrect column
indices: csr_inds[{}:{}] == {}".format(msg_prefix, a, b, csr_inds[a:b])
assert all([(j in csr_inds[a:b] for j in G[i].keys())]), "{}. However, it may have missing or incorrect
column indices: csr_inds[{}:{}] == {}".format(msg_prefix, a, b, csr_inds[a:b])

print ("n(Passed.)")

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Smartsolutions. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $10.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

81989 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$10.49
  • (0)
  Add to cart