In this paper, a new identification method for large heterogeneous spatially interconnected systems is presented. A string of different systems in state-space representation is considered. The proposed algorithm optimizes the Output-Error of the global system by using the Steepest-Descent and the Gauss-Newton methods. The main contribution of this work is that both the Jacobian and the Hessian matrix can be entirely captured by using Sequentially Semi-Separable (SSS) matrices. Therefore, all the computations in the optimization routine can be performed with complexity that is linear in the number of subsystems. This fact permits to obtain models for large interconnected systems at low computational cost. Finally, a numerical example is presented in order to show the effectiveness of the proposed algorithm.