Global illumination is the problem of rendering images by simulating the light transport in a scene, also considering the inter-reflection of light between surfaces. One general approach to global illumination that gained popularity during the last decade is the many-light formulation, whose idea is to approximate global illumination by many automatically generated virtual point lights. In this thesis, we address two fundamental issues that arise with the many-light formulation: scalability and generality. We present a new view of the many-light approach, by treating it as a large matrix of light-surface contributions. Our insight is that there is usually a significant amount of structure and redundancy in the matrix; this suggests that only a tiny subset of the elements might be needed for accurate reconstruction. First, we present a scalable rendering algorithm that exploits this insight by sampling a small subset of matrix rows and columns to reconstruct the image. This algorithm is very flexible in terms of the material and light types it can handle, and achieves high-quality rendering of complex scenes in several seconds on consumer-level graphics hardware. Furthermore, we extend this approach to render whole animations, by considering a 3D tensor of light-surface contributions over time. This allows us to further decrease the necessary number of samples by exploiting temporal coherence. We also address a long-standing limitation of all previous many-light approaches that leads to fundamentally incorrect results in scenes with glossy materials, by introducing a new virtual light type that does not have this limitation. Finally, we describe an algorithm that computes a wavelet-compressed approximation to the lighting matrix, which allows for interactive light placement in a scene with global illumination.