A multi-lithology diffusive stratigraphic model is considered, which simulates at large scales in space and time the infill of sedimentary basins governed by the interaction between tectonics displacements, eustatic variations, sediment supply, and sediment transport laws. The model accounts for the mass conservation of each sediment lithology resulting in a mixed parabolic, hyperbolic system of partial differential equations (PDEs) for the lithology concentrations and the sediment thickness. It also takes into account a limit on the rock alteration velocity modeled as a unilaterality constraint. To obtain a robust, fast, and accurate simulation, fully and semi-implicit finite volume discre tization schemes are derived for which the existence of stable solutions is proved. Then, the set of nonlinear equations is solved using a Newton algorithm adapted to the unilaterality constraint, and preconditioning strategies are defined for the solution of the linear system at each Newton iteration. They are based on an algebraic approximate decoupling of the sediment thickness and the concentration variables as well as on a proper preconditioning of each variable. These algorithms are studied and compared in terms of robustness, scalability, and efficiency on two real basin test cases.