  Due to the advent of multicore architectures and massive parallelism, the
tiled Cholesky factorization algorithm has recently received plenty of
attention and is often referenced by practitioners as a case study. It is also
implemented in mainstream dense linear algebra libraries. However, we note that
theoretical study of the parallelism of this algorithm is currently lacking. In
this paper, we present new theoretical results about the tiled Cholesky
factorization in the context of a parallel homogeneous model without
communication costs. We use standard flop-based weights for the tasks. For a
$t$-by-$t$ matrix, we know that the critical path of the tiled Cholesky
algorithm is $9t-10$ and that the weight of all tasks is $t^3$. In this
context, we prove that no schedule with less than $0.185 t^2$ processing units
can finish in a time less than the critical path. In perspective, a naive bound
gives $0.11 t^2.$ We then give a schedule which needs less than $0.25
t^2+0.16t+3$ processing units to complete in the time of the critical path. In
perspective, a naive schedule gives $0.50 t^2.$ In addition, given a fixed
number of processing units, $p$, we give a lower bound on the execution time as
follows: $$\max( \frac{t^{3}}{p}, \frac{t^{3}}{p} - 3\frac{t^2}{p} + 6\sqrt{2p}
- 7 , 9t-10).$$ The interest of the latter formula lies in the middle term. Our
results stem from the observation that the tiled Cholesky factorization is much
better behaved when we schedule it with an ALAP (As Late As Possible) heuristic
than an ASAP (As Soon As Possible) heuristic. We also provide scheduling
heuristics which match closely the lower bound on execution time. We believe
that our theoretical results will help practical scheduling studies. Indeed,
our results enable to better characterize the quality of a practical schedule
with respect to an optimal schedule.
