A second order accurate numerical scheme is proposed and implemented for the Landau-Lifshitz-Gilbert equation, which models magnetization dynamics in ferromagnetic materials, with large damping parameters. The main advantages of this method are associated with the following features: (1) It only solves linear systems of equations with coefficient matrices independent of the magnetization, and fast solvers are available, so that the numerical efficiency has been greatly improved, in comparison with the existing Gauss-Seidel project method. (2) The second-order accuracy in time is achieved, and it is unconditionally stable for large damping parameters. Moreover, both the second-order accuracy and the great efficiency improvement will be verified by several numerical examples in the 1D and 3D simulations. In the presence of large damping parameters, it is observed that this method is unconditionally stable and finds physically reasonable structures while many existing methods have failed. For the domain wall dynamics, the linear dependence of wall velocity with respect to the damping parameter and the external magnetic field will be obtained through the reported simulations.