Not knowing anything else about the matrix, I can only suggest another alternative to the determinant (which sounds like it's prohibitively time-consuming). 

If `m` is your matrix, try to find a root (or minimum) of 

    Min@Diagonal@SingularValueDecomposition[m][[2]]

instead. Unfortunately, `SingularValueDecomposition` is also very time consuming, but as I said, I don't know your matrix and therefore you may be lucky and it works. The lowest singular value will become zero when the matrix is singular.