Matrix Compression with Support for Algebraic Operations in Small Space
DOI:
https://doi.org/10.5753/reic.2025.6146Keywords:
Compression Algorithms, Matrix Compression, Compressed Linear Algebra, Matrix Multiplication, Grammar CompressionAbstract
This work investigates strategies to reduce memory consumption in matrix compression supporting algebraic operations directly on the compressed representation. In particular, we show how to modify the method mm-RePair [Ferragina et al., 2022] by performing the compression of large matrices in a partitioned manner, dividing them into blocks of consecutive rows, which are processed sequentially using less memory. The proposed method preserves support for multiplication operations on the compressed data and, although it causes a slight degradation in compression ratio, significantly reduces memory consumption as the number of blocks increases, enabling its application in scenarios where the matrix is larger than the available memory.
Downloads
References
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mane, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viegas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. (2016). Tensorflow: Large-scale machine learning on heterogeneous distributed systems. DOI: 10.48550/arXiv.1603.04467.
Bhattacherjee, S., Deshpande, A., and Sussman, A. (2014). Pstore: an efficient storage framework for managing scientific data. In Jensen, C. S., Lu, H., Pedersen, T. B., Thomsen, C., and Torp, K., editors, Conference on Scientific and Statistical Database Management, SSDBM ’14, Aalborg, Denmark, June 30 - July 02, 2014, pages 25:1–25:12. ACM. DOI: 10.1145/2618243.2618268.
Elgohary, A., Boehm, M., Haas, P. J., Reiss, F. R., and Reinwald, B. (2018). Compressed linear algebra for large-scale machine learning. VLDB J., 27(5):719–744. DOI: 10.1007/S00778-017-0478-1.
Elgohary, A., Boehm, M., Haas, P. J., Reiss, F. R., and Reinwald, B. (2019). Compressed linear algebra for declarative large-scale machine learning. Commun. ACM, 62(5):83–91. DOI: 10.1145/3318221.
Ferragina, P., Manzini, G., Gagie, T., Köppl, D., Navarro, G., Striani, M., and Tosoni, F. (2022). Improving matrix-vector multiplication via lossless grammar-compressed matrices. Proc. VLDB Endow., 15(10):2175–2187. DOI: 10.14778/3547305.3547321.
Larsson, N. J. and Moffat, A. (1999). Offline dictionary-based compression. In Data Compression Conference, DCC 1999, Snowbird, Utah, USA, March 29-31, 1999, pages 296–305. IEEE Computer Society. DOI: 10.1109/DCC.1999.755679.
Navarro, G. (2016). Compact Data Structures - A Practical Approach. Cambridge University Press.
Saad, Y. (2003). Iterative methods for sparse linear systems. SIAM.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 The authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
