How big is A? Note that A^{-0.5} will most likely be dense (since even inverses of sparse matrices are dense), so you’d be restricted to small systems. If that’s the case, then maybe you could operate on its spectral decomposition:
A = V D V^T
A^{-1} = V^T D^{-1} V
A^{-0.5} = V^T D^{-0.5} V
With V the eigenvectors and D the diagonal matrix of eigenvalues.
Which assumes that A is symmetric, as you’ve indicated.