Computational Linear Algebra Questions

[Bhargavaa1]

Hey Mike and the class,
Thanks for a great review session today. I have some remaining questions from the Computational Linear Algebra Notes:

1. Is it possible to add two matrices (A+B) where one is sparse (A:mxn) and the other is dense (B:mxn)? If so, would the runtime be $\theta(mn)$?
2. What does the L2 norm for a matrix signify?
3. I know that nnz(A) = O(1) means that the number of non-zero entries in A is bounded by an arbitrary constant. Does that mean we can consider the zero matrix in these types of situations as 0 is upper bounded by O(1)?

Thanks,
Adi

[mikeizbicki]

1. Is it possible to add two matrices (A+B) where one is sparse (A:mxn) and the other is dense (B:mxn)? If so, would the runtime be $\theta(mn)$?

I won't ask this on the midterm. However, if you're modifying the dense matrix (using the pytorch add_ family of functions), the runtime will be $\Theta(nnz(A))$ and if you're making a copy and storing the result in the copy, the runtime is $\Theta(mn)$.

2. What does the L2 norm for a matrix signify?

The top eigenvector. Using the pagerank paper notation, it is a correct statement (and one you should understand) that $\pi = \lVert \bar{\bar P}\rVert$.

3. I know that nnz(A) = O(1) means that the number of non-zero entries in A is bounded by an arbitrary constant. Does that mean we can consider the zero matrix in these types of situations as 0 is upper bounded by O(1)?

That is correct. $0 = O(1)$. I made a mistake in the review session where I said that $0 = \Omega(1)$, but that is incorrect, and the correct statement is $0 \ne \Omega(1)$.

[Bhargavaa1]

Thanks for answering and clarifying.