  We study fundamental problems in linear algebra, such as finding a maximal
linearly independent subset of rows or columns (a basis), solving linear
regression, or computing a subspace embedding. For these problems, we consider
input matrices $\mathbf{A}\in\mathbb{R}^{n\times d}$ with $n > d$. The input
can be read in $\text{nnz}(\mathbf{A})$ time, which denotes the number of
nonzero entries of $\mathbf{A}$. In this paper, we show that beyond the time
required to read the input matrix, these fundamental linear algebra problems
can be solved in $d^{\omega}$ time, i.e., where $\omega \approx 2.37$ is the
current matrix-multiplication exponent.
  To do so, we introduce a constant-factor subspace embedding with the optimal
$m=\mathcal{O}(d)$ number of rows, and which can be applied in time
$\mathcal{O}\left(\frac{\text{nnz}(\mathbf{A})}{\alpha}\right) + d^{2 +
\alpha}\text{poly}(\log d)$ for any trade-off parameter $\alpha>0$, tightening
a recent result by Chepurko et. al. [SODA 2022] that achieves an
$\exp(\text{poly}(\log\log n))$ distortion with $m=d\cdot\text{poly}(\log\log
d)$ rows in
$\mathcal{O}\left(\frac{\text{nnz}(\mathbf{A})}{\alpha}+d^{2+\alpha+o(1)}\right)$
time. Our subspace embedding uses a recently shown property of stacked
Subsampled Randomized Hadamard Transforms (SRHT), which actually increase the
input dimension, to "spread" the mass of an input vector among a large number
of coordinates, followed by random sampling. To control the effects of random
sampling, we use fast semidefinite programming to reweight the rows. We then
use our constant-factor subspace embedding to give the first optimal runtime
algorithms for finding a maximal linearly independent subset of columns,
regression, and leverage score sampling. To do so, we also introduce a novel
subroutine that iteratively grows a set of independent rows, which may be of
independent interest.
