We present acceleration of the vibrational frequency calculations required in free energy basin-hopping (FEBH) global optimisation using sparse Cholesky factorisation. We describe an interface with the SuiteSparse software package that facilitates these calculations, and present results detailing the accuracy and speedups obtained for atomic clusters and biomolecules. For the larger systems, exploiting sparsity reduces the computational cost by factors of ten to thirty, with no significant loss in accuracy. This approach will therefore provide access to the vibrational density of states, and hence to local harmonic free energies, for structure prediction and thermodynamic properties of more complex systems.