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 <A HREF="https://en.wikipedia.org/wiki/Chordal_graph">chordal graph</A> (no minimal cycle of length $\geq 4$).     

There exist efficient tests for chordality, see <A HREF="https://on-demand.gputechconf.com/gtc/2016/presentation/s6489-agnieszka-lupinska-testing-chordal-graphs-with-cuda.pdf">Testing Chordal Graphs with CUDA</A>. (If have understood this algorithm correctly, it takes $O(N)$ time.)