• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 2 fuera de 6 páginas
Examen

Compressed Sparse Row Format Answer

Document preview thumbnail
Vista previa 2 fuera de 6 páginas

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.)")

Vista previa del contenido

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.)")

Información del documento

Subido en
18 de enero de 2022
Número de páginas
6
Escrito en
2021/2022
Tipo
Examen
Contiene
Preguntas y respuestas
$10.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Smartsolutions
3.9
(520)
Vendido
2972
Seguidores
2545
Artículos
1165
Última venta
2 días hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes