In the Portable, Extensible Toolkit for Scientific Computing (PETSc), the user often creates matrices and vectors. These objects are then used as input for other routines like iterative solvers.
PETSc offers a routine for preallocating matrix memory by providing the number of nonzero entries in the diagonal submatrix and the off diagonal submatrices.
MATLAB has some useful articles about why preallocation helps -- for example, it eliminates the need to reallocate memory every time an element is added to a vector.
Why does memory preallocation in PETSc help so much? What exactly is happening when I tell PETSc the number of nonzeros in my matrix, and how does it compare to when I do not preallocate?
I found a partial answer in this powerpoint about how the preallocation is related to the AIJ format. It says that PETSc sparse matrices are dynamic objects and can have nonzeros added to them on the fly. But this "on the fly" approach can lead to extra copying and reallocating, etc. I suppose this is the answer I wanted, but more details would be great.