Try A = LU decomp first (if applicable, even go for Cholesky if possible). Then, (if L and U are invertable), inv(A) = inv(LU) = inv(U) * inv(L), and inverting L and U are quick. Well, this works for me, 0.13 sec for 100x100, 18 sec for 500x500, 260 sec for 1000x1000, and my laptop is a dinosaur.