stbmm routines multiply a symmetric, block-diagonal matrix, with Toeplitz banded blocks by a data matrix. This operation is in fact construed as a product of a series of Toeplitz blocks by the data matrix. The Toeplitz blocks are each defined as any Toeplitz matrix (see, e.g., Functionality and definitions above) and have in particular defined a range - an interval of the data matrix rows to which it should be applied. The ranges of any two Toeplitz matrices must not overlap. The limits of the interval can be looked at as defining the position of each Toeplitz block within a single Toeplitz-block diagonal matrix of the size equal that of a number of rows of the data matrix. What the routine then does it is to multiply each block by a respective subblock of the data matrix. The rows of the data matrix, which do not belong to the interval of any block are copied unchanged, meaning that the corresponding blocks of the Toeplitz matrix are implicitly assumed to be equal to .

In the MPI implementation each processor needs only those of all the Toeplitz blocks which have ranges overlapping with part of the data matrix assigned to it. If more are defined on the input they are ignored. Note that this is the user's responsibility to ensure that the Toeplitz matrices are assigned to different processes in a consistent way meaning they represent a product of a series of diagonal Toeplitz blocks. It is important to observe that the block distribution will in general depend on the assumed distribution pattern for the data matrix. This is discussed in the examples below.

If a Toeplitz block corresponds to the data matrix parts assigned to two (or more) processes, the Toeplitz block parameters have to be the same on all implicated processes, as each process will use them to define the amount of data which needs communicate to its neighbors. In general, each process calculates products of the Toeplitz blocks by the corresponding part of the data matrix. If a Toeplitz block corresponds to data of more than one process then the communication is used to copy necessary data to enable such a multiplication locally.