Our goal is to minimize the communication costs of Krylov Subspace Methods (KSMs) to solve either Ax = b or Ax =λx, when A is a large sparse matrix. By communication costs we mean both bandwidth and latency costs, either between processors on a parallel computer, or between levels of a memory hierarchy on a sequential computer. As the cost of communication is growing exponentially relative to computation on modern computers, reducing communication is becoming ever more important. It is possible to reduce communication costs to near their theoretical minima: On a parallel computer this means latency costs are independent of the dimension k of the Krylov subspace, as opposed to growing proportionally to k for a conventional implementation. On a sequential computer, this mean latency and bandwidth costs are independent of k. Achieving this speedup requires a new algorithmic formulation of KSMs. In this paper we present just part of this new formulation, namely computing a basis ofthe Krylov subspace spanned by [x, Ax,A2x, ...Akx]; other papers will present the rest of the KSM formulation. We present theory, performance models, and computational results: Our parallel performance models of 2D and 3D model problems predict speedups over a conventional algorithm of up to 15x on a model Petaflop machine, and up to 22x on a model of the Grid. Our sequential performance models of the same model problems predict speedups over a conventional algorithm of up to 10x on an out-of-core implementation, and up to 2.5x on Intel Clovertown, where we use our ideas to reduce off-chip latency and bandwidth to DRAM. Finally, we measured a speedup of over 3x on an actual out-of-core implementation. We also consider the related kernel [Ax,MAx,AMAx, ...,A(MA)k−1x, (MA)kx], which arises in preconditioned KSMs. Under certain mathematical conditions on A and the preconditioner M, we show how to avoid latency and bandwidth for this kernel as well.