The Dulmage-Mendelsohn permutation in seismic tomography

Seismic tomography inverse problems are among the largest high-dimensional parameter estimation tasks in Earth science. Although iterative algorithms can be used to efficiently solve these problems, their size gives rise to several issues such as the intractability of the computation of the model resolution and the model posterior covariance matrices that provide the means of assessing the robustness of the solution. In this work, we utilize methods from combinatorics and graph theory to study the structure of typical regional seismic body-wave tomography problems, and to effectively decompose them into subsets that can be solved efficiently by means of the least squares method. In combination with recent high performance direct sparse algorithms, this reduction in dimensionality allows for an efficient computation of the model resolution and covariance matrices using limited resources. We apply this methodology to a moderate size imaging of the structure of the crust and the upper mantle beneath Japan using deep local earthquakes recorded by the High Sensitivity Seismograph Network stations. Among the prominent features that are being imaged is a strong low-velocity region beneath the subducting Pacific slab along the entire Japan trench