An algorithm for partially relaxing multiwell energy densities, such as for materials undergoing martensitic phase transitions, is presented here. The detection of the rank-one convex hull, which describes effective properties of such materials, is carried out for the most prominent nontrivial case, namely the so-called T-k-configurations. Despite the fact that the computation of relaxed energies (and with it effective properties) is inherently unstable, we show that the detection of these hulls (T-4-configurations) can be carried out exactly and with high efficiency. This allows in practice for their computation to arbitrary precision. In particular, our approach to detect these hulls is not based on any approximation or grid-like discretization. This makes the approach very different from previous (unstable and computationally expensive) algorithms for the computation of rank-one convex hulls or sequential-lamination algorithms for the simulation of martensitic microstructure. It can be used to improve these algorithms. In cases where there is a strict separation of length scales, these ideas can be integrated at a sub-grid level to macroscopic finite-element computations. The algorithm presented here enables, for the first time, large numbers of tests for T-4-configurations. Stochastic experiments in several space dimensions are reported here. (C) 2004 Academie des sciences. Published by Elsevier SAS. All rights reserved.