We present a new method for solving the Redfield equation, which describes the evolution of the reduced density matrix of a multilevel quantum-mechanical system interacting with a thermal bath. The method is based on a new decomposition of the Redfield relaxation tensor that makes possible its direct application to the density matrix without explicit construction of the full tensor. In the resulting expressions, only ordinary matrices are involved and so any quantum system whose Hamiltonian can be diagonalized can be treated with the full Redfield theory. To efficiently solve the equation of motion for the density matrix, we introduce a generalization of the short-iterative-Lanczos propagator. Together, these contributions allow the complete Redfield theory to be applied to significantly larger systems than was previously possible. Several model calculations are presented to illustrate the methodology, including one example with 172 quantum states.