Compressão de Matrizes com Suporte a Operações Algébricas Utilizando Pouca Memória
DOI:
https://doi.org/10.5753/reic.2025.6146Keywords:
Algoritmos de Compressão, Compressão de Matrizes, Compressed Linear Algebra, Multiplicação de Matrizes, Compressão GramaticalAbstract
Este trabalho investiga estratégias para reduzir o consumo de memória durante a compressão de matrizes com suporte a operações algébricas diretamente sobre a representação comprimida. Em particular, mostramos como modificar o método mm-RePair [Ferragina et al., 2022] realizando a compressão de grandes matrizes de forma particionada, dividindo-as em blocos de linhas consecutivas, que são processados sequencialmente utilizando menos memória. O método proposto mantém o suporte a operações de multiplicação sobre os dados comprimidos e, embora provoque uma pequena piora na taxa de compressão, reduz significativamente o consumo de memória conforme o número de blocos aumenta, possibilitando a sua aplicação em situações em que a matriz é maior do que a memória disponível.
Downloads
Referências
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
Como Citar
Issue
Section
Licença
Copyright (c) 2025 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
