Due to peripheral nerve stimulation, the magnetic particle imaging (MPI) method is limited in the maximum applicable excitation-field amplitude. This in turn leads to a limitation of the size of the covered field of view (FoV) to few millimeters. In order to still capture a larger FoV, MPI is capable to rapidly acquire volumes in a multi-patch fashion. To this end, the small excitation volume is shifted through space using the magnetic focus fields. Recently, it has been shown that the individual patches are preferably reconstructed in a joint fashion by solving a single linear system of equations taking the coupling between individual patches into account. While this improves the image quality, it is computationally and memory demanding since the size of the linear system increases in the best case quadratically with the number of patches. In this paper, we will develop a reconstruction algorithm for MPI multi-patch data exploiting the sparsity of the joint system matrix. A highly efficient implicit matrix format allows for rapid on-the-fly calculations of linear algebra operations involving the system matrix. Using this approach, the computational effort can be reduced to a linear dependence on the number of used patches. The algorithm is validated on 3-D multi-patch phantom data sets and shown to reconstruct large data sets with 15 patches in less than 22 s.