"For example, we know precisely how long our algorithms take to multiply and factor matrices." . At least in the case of matrix multiplication the technically correct statement is we have an upper bound on how long it takes to multiply matrices. Current best is O(n^2.37) and I believe that O(n^2) is still believed to be the optimat number (perhaps n^{2 +\epsilon} is correct)
I chose my words carefully there. I didn't say "we know what the optimal algorithm is for matrix factorization." Because there, you are right. We don't know the answer. Instead, I wrote "we know precisely how long our algorithms take to multiply." This refers to the deterministic algorithms implemented in BLAS and LAPACK.
"For example, we know precisely how long our algorithms take to multiply and factor matrices." . At least in the case of matrix multiplication the technically correct statement is we have an upper bound on how long it takes to multiply matrices. Current best is O(n^2.37) and I believe that O(n^2) is still believed to be the optimat number (perhaps n^{2 +\epsilon} is correct)
I chose my words carefully there. I didn't say "we know what the optimal algorithm is for matrix factorization." Because there, you are right. We don't know the answer. Instead, I wrote "we know precisely how long our algorithms take to multiply." This refers to the deterministic algorithms implemented in BLAS and LAPACK.