Applications for EDM include: molecular conformation problems in chemistry; multidimensional scaling and multivariate analysis problems in statistics; genetics, geography, etc...
We present two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant.
We conclude with numerical tests.