The compression of three-dimensional ultraspectral sounder data is a challenging task given its unprecedented size. We develop a fast precomputed vector quantization (FPVQ) scheme with optimal bit allocation for lossless compression of ultraspectral sounder data. The scheme consists of linear prediction, bit-depth partitioning, vector quantization, and optimal bit allocation. Linear prediction serves as a whitening tool to make the prediction residuals of each channel close to a Gaussian distribution, and then these residuals are partitioned based on bit depths. Each partition is further divided into several sub-partitions with various 2^k channels for vector quantization. Only the codebooks with 2^m codewords for 2^k -dimensional normalized Gaussian distributions are precomputed. A new algorithm is developed for optimal bit allocation among sub-partitions. Unlike previous algorithms that may yield a sub-optimal solution, the proposed algorithm guarantees to find the minimum of the cost function under the constraint of a given total bit rate. Numerical experiments upon the NASA AIRS data show that the FPVQ scheme gives high compression ratios for lossless compression of ultraspectral sounder data.