This characterization might be useful: The partial matrix $M$ can be associated with an undirected graph $G$ ($n$ vertices, with vertex $i$ and $j$ connected if $M_{ij}$ is specified). The matrix has a PSD completion if and only if $G$ is a chordal graph (no minimal cycle of length $\geq 4$).

There exist efficient tests for chordality, see Testing Chordal Graphs with CUDA. (If have understood this algorithm correctly, it takes $O(N)$ time.)

This sufficient condition (thank you, Daniel) might be useful: The partial matrix $M$ can be associated with an undirected graph $G$ ($N$ vertices, with vertex $i$ and $j$ connected if $M_{ij}$ is specified). If $G$ is a chordal graph (no minimal cycle of length $\geq 4$) then the matrix $M$ has a PSD completion.

There exist efficient tests for chordality, see Testing Chordal Graphs with CUDA. (If have understood this algorithm correctly, it takes $O(N)$ time.)

This characterization might be useful: The partial matrix $M$ can be associated with an undirected graph $G$ ($n$ vertices, with vertex $i$ and $j$ connected if $M_{ij}$ is specified). The matrix has a PSD completion if and only if $G$ is a chordal graph (no minimal cycle of length $\geq 4$. There exist efficient tests for chordality, see Testing Chordal Graphs with CUDA.

This characterization might be useful: The partial matrix $M$ can be associated with an undirected graph $G$ ($n$ vertices, with vertex $i$ and $j$ connected if $M_{ij}$ is specified). The matrix has a PSD completion if and only if $G$ is a chordal graph (no minimal cycle of length $\geq 4$). 

There exist efficient tests for chordality, see Testing Chordal Graphs with CUDA. (If have understood this algorithm correctly, it takes $O(N)$ time.)