The purpose of the paper is to present a new and fast algorithm for solving the sparse- and dense-data surface smoothing problems using a membrane, thin-plate, or thin-plate membrane spline for data containing discontinuities. These problems are formulated as solutions to a Lyapunov matrix equation or a cascade of two Lyapunov matrix equations with an appropriate right-hand-side by using the Sherman-Morrison-Woodbury formula of matrix analysis. The efficiency of the algorithm is demonstrated through experiments on sparse-data surface smoothing. The numerical results are compared to the conjugate gradient algorithm and the hierarchical-basis preconditioned conjugate gradient algorithm.