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.