An Asynchronous Parallel Randomized Kaczmarz Algorithm
  We describe an asynchronous parallel variant of the randomized Kaczmarz (RK) algorithm for solving the linear system $Ax=b$. The analysis shows linear convergence and indicates that nearly linear speedup can be expected if the number of processors is bounded by a multiple of the number of rows in $A$. 
Ji Liu and Stephen J. Wright and Srikrishna Sridhar
math.NA cs.NA math.OC