We study approximation techniques for incompressible flows with heterogeneous properties. Speci cally, we study two types of phenomena. The first is the flow of a viscous incompressible fluid through a rigid porous medium, where the permeability of the medium depends on the pressure. The second is the ow of a viscous incompressible fluid with variable density. The heterogeneity is the permeability and the density, respectively. For the first problem, we propose a finite element discretization and, in the case where the dependence on the pressure is bounded from above and below, we prove its convergence to the solution and propose an algorithm to solve the discrete system. In the case where the dependence is exponential, we propose a splitting scheme which involves solving only two linear systems. For the second problem, we introduce a fractional time-stepping scheme which, as opposed to other existing techniques, requires only the solution of a Poisson equation for the determination of the pressure. This simpli cation greatly reduces the computational cost. We prove the stability of first and second order schemes, and provide error estimates for first order schemes. For all the introduced discretization schemes we present numerical experiments, which illustrate their performance on model problems, as well as on realistic ones.