Both prediction and completion steps make use of a matrix R defined as a geometric series derived from a matrix P,
Both P and R are indexed by the nonterminals in the grammar. The matrix P is derived from the SCFG rules and probabilities (either the left-corner relation or the unit-production relation).
For an application using a fixed grammar the time taken by the precomputation of left-corner and unit-production matrices may not be crucial, since it occurs off-line. There are cases, however, when that cost should be minimized, e.g., when rule probabilities are iteratively reestimated.
Even if the matrix P is sparse, the matrix inversion
can be prohibitive for large numbers of nonterminals n.
Empirically, matrices of rank n with a bounded number p of non-zero
entries in each row (i.e., p is independent of n) can be inverted in
time , whereas a full
matrix of size would require time 
.
In many cases the grammar has a relatively small number of nonterminals that have productions involving other nonterminals in a left-corner (or the RHS of a unit-production). Only those nonterminals can have non-zero contributions to the higher powers of the matrix P. This fact can be used to substantially reduce the cost of the matrix inversion needed to compute R.
Let P' be a subset of the entries of P, namely, only those elements indexed by nonterminals that have a non-empty row in P. For example, for the left-corner computation, P' is obtained from P by deleting all rows and columns indexed by nonterminals that do not have productions starting with nonterminals. Let I' be the identity matrix over the same set of nonterminals as P'. Then R can be computed as
Here R' is the inverse of I' - P', and denotes a matrix multiplication in which the left operand is first augmented with zero elements to match the dimensions of the right operand, P.
The speedups obtained with this technique can be substantial.
For a grammar with 789 nonterminals, of which only 132 have nonterminal
productions, the left-corner matrix was computed in 12 seconds (including
the final multiply with P and addition of I).
Inversion of the full matrix I - P took 4 minutes 28 seconds.