We propose a matrix-free inexact preconditioned solution strategy for elliptic partial differential equations discretized by the Galerkin method on structured grids. We base our preconditioner on an approximation of the discrete linear operator by a sum of Kronecker product matrices. The action of the inverse of the approximation on a vector of coefficients is approximated by an inner preconditioned Conjugate Gradient solver. The forward problem is solved by an inexact preconditioned variant of the Conjugate Gradient method. The complexity of the Kronecker matrix-vector product in the inner iteration is lower than the complexity of the matrix-vector product product for the forward problem, leading to a fast solution strategy, significantly reduced numbers of iterations and performance gains. The proposed method is implemented in our open-source Julia framework for spline based discretization methods. We show the robustness, efficiency and effectiveness of our approach for benchmark problems in linear elasticity and heat conduction, and illustrate the performance gain with respect to the state-of-the-art Fast Diagonalization and approximate Kronecker inverse preconditioning techniques.