As high performance Linux clusters enter mainstream supercomputing, it is important to understand how well these architecture scale for important kernels in computational science applications, such as linear solvers, eigenvalue solvers, multidimensional FFT's. This paper attempts to characterize the scalability of state of the art linear solvers on large Linux clusters. Our studies focus on two families of algorithms, Krylov subspace methods and multigrid methods. We include results up to 256 processors on a Linux cluster, with problem sizes up to 64 million unknowns.