Ultrasound transmission tomography offers quantitative characterization of the tissue or materials by their speed of sound and attenuation. Reconstruction of such images is an inverse problem which is solved iteratively based on a forward model of the Helmholtz equation by paraxial approximation and thus is time-consuming. Hence, developing optimizers that decrease this time, in particular reducing the number of forward propagations is of high relevance in order to bring this technology into clinical practice. In this paper, we solve the inverse problem of reconstruction in a two-level strategy, by an outer and an inner loop. At each iteration of the outer loop, the system is linearized and this linear subproblem is solved in the inner loop with a preconditioned conjugate gradient (CG). A standard Cholesky preconditioning method based on the system matrix is compared with a matrix-free Quasi-Newton update approach, where a preconditioned matrix-vector product is computed at the beginning of every CG iteration. We also use a multigrid scheme with multi-frequency reconstruction to get a convergent rough reconstruction at a lower frequ ... mehrency and then refine it on a higher-resolution grid. The Cholesky preconditioning reduces the number of CG iterations by approx. 70%~85%; but the computation time for determining the system matrix for the Cholesky preconditioner is dominating, offsetting the gains of the reduction of iterations. The matrix-free preconditioning method saves approx. 30% of the computation time on average for single-frequency and multi-frequency reconstruction. For the robust multifrequency reconstruction, we test three breast-like numerical phantoms resulting in a deviation of 0.13 m/s on average in speed of sound reconstruction and a deviation of 5.4% on average in attenuation reconstruction, from the ground truth simulation.