It can be computationally expensive to solve the linear regression problems. Actually, the nth-order partial correlation (i.e., with |Z| = n) can be easily computed from three (n - 1)th-order partial correlations. The zeroth-order partial correlation ρXY·Ø is defined to be the regular correlation coefficient ρXY. It holds, for any that Naïvely implementing this computation as a recursive algorithm yields an exponential time complexity. However, this computation has the overlapping subproblems property, such that using dynamic programming or simply caching the results of the recursive calls yields a complexity of . Note in the case where Z is a single variable, this reduces to: Using matrix inversion The partial correlation can also be written in terms of the joint precision matrix. Consider a set of random variables, of cardinality n. We want the partial correlation between two variables and given all others, i.e., . Suppose the (joint/full) covariance matrix is positive definite and therefore invertible. If the precision matrix is defined as , then Computing this requires , the inverse of the covariance matrix which runs in time (using the sample covariance matrix to obtain a sample partial correlation). Note that only a single matrix inversion is required to give all the partial correlations between pairs of variables in . To prove Equation (), return to the previous notation (i.e. ) and start with the definition of partial correlation: ρXY·Z is the correlation between the residuals eX and eY resulting from the linear regression of X with Z and of Y with Z, respectively. First, suppose are the coefficients for linear regression fit; that is, Write the joint covariance matrix for the vector as whereThen the standard formula for linear regression gives Hence, the residuals can be written as Note that has expectation zero because of the inclusion of an intercept term in . Computing the covariance now gives Next, write the precision matrix in a similar block form: Then, by Schur's formula for block-matrix inversion, The entries of the right-hand-side matrix are precisely the covariances previously computed in (), giving Using the formula for the inverse of a 2×2 matrix gives So indeed, the partial correlation is as claimed in (). Interpretation Geometrical Let three variables X, Y, Z (where Z is the "control" or "extra variable") be chosen from a joint probability distribution over n variables V. Further, let vi, 1 ≤ i ≤ N, be N n-dimensional