Over the past two decades, ab initio nuclear structure calculations of atomic nuclei have seen major advances. The use of systematically improvable methods with controlled truncations has enabled studies over a large range of mass numbers and for a diverse set of nuclear observables. These developments were mainly driven by wave-function expansion methods that are based on a many-body expansion around a reference state, while admitting a mild computational scaling in mass number. However, substantial increases in computational cost and memory requirements when describing heavier and more exotic nuclei or when aiming at more precise predictions still present severe challenges in ab initio theory. In this thesis, we address these challenges and present promising approaches that allow to extend current frontiers and enable converged ab initio calculations for higher mass numbers and with increased precision. We study light, medium-mass, and heavy closed-shell nuclei within the in-medium similarity renormalization group (IMSRG) using two- and three-body interactions derived within the framework of chiral effective field theory. In particular, we investigate optimizations of the reference state using the natural orbital basis, employ importance-truncation techniques to compress many-body operators, and apply a new normal-ordering framework that allows to circumvent standard truncations when including three-nucleon interactions. The natural orbital basis, defined as the eigenbasis of a perturbatively improved one-body density matrix, is explored in detail. Significant benefits in many-body calculations are obtained using truncated natural orbitals that are constructed in a large space and applied in a reduced space for the many-body solution. This approach results in faster model-space convergence and frequency-independent ground-state observables. Furthermore, we demonstrate how importance-truncation techniques can be applied in the IMSRG to compress many-body operators and to substantially reduce the memory requirements. Considering only the most important contributions of the two-body operators, a major part of the matrix elements can be neglected while introducing only minor errors in medium-mass nuclei. Both advances using natural orbitals and importance-truncation techniques are also of great interest for relaxing the presently established many-body truncation in the IMSRG approach, which is currently prohibitive beyond small model spaces due to the tremendous increase in computational costs. The explicit inclusion of three-body operators provides additional computational challenges for ab initio calculations. Standard normal-ordering applications to approximate three-body interactions typically necessitate a truncation on the number of three-body matrix elements, which becomes significant for calculations of heavy nuclei. The novel normal-ordering framework in this thesis avoids this truncation and requires substantially less memory by performing the normal ordering directly in the Jacobi basis. We systematically study the convergence behavior and explore benefits of the new framework for light up to heavy nuclei, especially targeting 132 Sn and 208 Pb. These developments open new ways for extending first-principle calculations of atomic nuclei to heavier and more exotic systems over the whole range of the nuclear chart.