Summary: Full waveform inversion (FWI) is a process in which seismic numerical simulations are fit to observed data by changing the wave velocity model of the medium under investigation. The problem is nonlinear, and therefore optimization techniques have been used to find a reasonable solution to the problem. The main problem in fitting the data is the lack of low spatial frequencies. This deficiency often leads to a local minimum and to nonplausible solutions. In this work we explore how to obtain low-frequency information for FWI. Our approach involves augmenting FWI with travel time tomography, which has low-frequency features. By jointly inverting these two problems we enrich FWI with information that can replace low-frequency data. In addition, we use high-order regularization, in a preliminary inversion stage, to prevent high-frequency features from polluting our model in the initial stages of the reconstruction. This regularization also promotes the nondominant low-frequency modes that exist in the FWI sensitivity. By applying a joint FWI and travel time inversion we are able to obtain a smooth model than can later be used to recover a good approximation for the true model. A second contribution of this paper involves the acceleration of the main computational bottleneck in FWI – the solution of the Helmholtz equation. We show that the solution time can be reduced by solving the equation for multiple right-hand sides using block multigrid preconditioned Krylov methods.