The authors discuss solving the depth interpolation problem on a parallel architecture, a fine-grained SIMD (single-instruction, multiple data stream) machine with local and global communication networks. Many constraint propagation problems in early vision, including depth interpolation, can be cast as solving a large system of linear equations where the resulting matrix is symmetric and positive definite (SPD). Usually, the resulting SPD matrix is sparse. The authors show how the adaptive Chebyshev acceleration and the conjugate gradient methods accelerated further with a multigrid approach can be run on this parallel architecture for sparse SPD matrices. They give numerical results for fairly large synthetic images, and compare them with the results from the Gauss-Seidel method accelerated also with a multigrid approach.>