  The randomized Kaczmarz ($\RK$) algorithm is a simple but powerful approach
for solving consistent linear systems $Ax=b$. This paper proposes an
accelerated randomized Kaczmarz ($\ARK$) algorithm with better convergence than
the standard $\RK$ algorithm on ill conditioned problems. The per-iteration
cost of $\RK$ and $\ARK$ are similar if $A$ is dense, but $\RK$ is much more
able to exploit sparsity in $A$ than is $\ARK$. To deal with the sparse case,
an efficient implementation for $\ARK$, called $\SARK$, is proposed. A
comparison of convergence rates and average per-iteration complexities among
$\RK$, $\ARK$, and $\SARK$ is given, taking into account different levels of
sparseness and conditioning. Comparisons with the leading deterministic
algorithm --- conjugate gradient applied to the normal equations --- are also
given. Finally, the analysis is validated via computational testing.
