We revisit the problem of computing submatrices of the Cramér-Rao bound (CRB), which lower bounds the variance of any unbiased estimator of a vector parameter $\vth$. We explore iterative methods that avoid direct inversion of the Fisher information matrix, which can be computationally expensive when the dimension of $\vth$ is large. The computation of the bound is related to the quadratic matrix program, where there are highly efficient methods for solving it. We present several methods, and show that algorithms in prior work are special instances of existing optimization algorithms. Some of these methods converge to the bound monotonically, but in particular, algorithms converging non-monotonically are much faster. We then extend the work to encompass the computation of the CRB when the Fisher information matrix is singular and when the parameter $\vth$ is subject to constraints. As an application, we consider the design of a data streaming algorithm for network measurement.