Sequencing-based spatial transcriptomics has revolutionized the study of tissue architecture, but its `spots' often contain multiple cells, creating a key computational challenge, termed deconvolution, to decipher each spot's cell-type composition. Reference-free deconvolution methods avoid the need for a matched single-cell RNA-seq dataset, but typically neglect the spatial correlation between neighboring spots and do not leverage modern hardware for efficient computation. Here, we propose SNMF (Spatial Non-negative Matrix Factorization): a rapid, accurate, and reference-free deconvolution method. SNMF extends the standard NMF framework with a spatial mixing matrix that models neighborhood influences, guiding the factorization toward spatially coherent solutions. Our R package is, to our knowledge, the first spatial transcriptomics deconvolution tool to natively support GPU execution, completing benchmark analyses in under one minute---over two orders of magnitude faster than the slowest competing methods---with moderate memory requirements. On synthetic and real benchmark datasets, SNMF significantly outperforms state-of-the-art methods in deconvolution accuracy, and on a human melanoma dataset it recovers biologically meaningful cell-type signatures---including a tumor-boundary transition zone---without any reference input. The proposed mehtod is publicly available at https://github.com/ML4BM-Lab/SNMF.