Problems

How fast can we do each of these?

• Let A be a sparse m by n matrix with l non-zero elements. For $1 \le i \le m$, $1 \le j \le n$, compute A[i,j].
• Let b be a dense 1 by m row vector. Let A be a sparse m by n matrix with l non-zero elements. Compute b times A.
• Same problem again, but let b be sparse with k non-zero elements.
• Let A be a sparse m by n matrix with l non-zero elements. Compute the transpose of A.
• Let A be a sparse m by n matrix with l non-zero elements. Let B be a sparse n by p matrix with k non-zero elements. Compute A times B.