- -

A fast sparse block circulant matrix vector product

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A fast sparse block circulant matrix vector product

Show simple item record

Files in this item

dc.contributor.author Romero Alcalde, Eloy es_ES
dc.contributor.author Tomás Domínguez, Andrés Enrique es_ES
dc.contributor.author Soriano Asensi, Antonio es_ES
dc.contributor.author Blanquer Espert, Ignacio es_ES
dc.date.accessioned 2016-09-26T09:38:29Z
dc.date.available 2016-09-26T09:38:29Z
dc.date.issued 2014-08-25
dc.identifier.isbn 978-3-319-09872-2
dc.identifier.issn 0302-9743
dc.identifier.uri http://hdl.handle.net/10251/70427
dc.description.abstract In the context of computed tomography (CT), iterative image reconstruction techniques are gaining attention because high-quality images are becoming computationally feasible. They involve the solution of large systems of equations, whose cost is dominated by the sparse matrix vector product (SpMV). Our work considers the case of the sparse matrices being block circulant, which arises when taking advantage of the rotational symmetry in the tomographic system. Besides the straightforward storage saving, we exploit the circulant structure to rewrite the poor-performance SpMVs into a high-performance product between sparse and dense matrices. This paper describes the implementations developed for multi-core CPUs and GPUs, and presents experimental results with typical CT matrices. The presented approach is up to ten times faster than without exploiting the circulant structure. es_ES
dc.language Inglés es_ES
dc.publisher Springer es_ES
dc.relation.ispartof Euro-Par 2014 Parallel Processing es_ES
dc.relation.ispartofseries Lecture Notes in Computer Science;8632
dc.rights Reserva de todos los derechos es_ES
dc.subject Circulant matrix es_ES
dc.subject Sparse matrix es_ES
dc.subject Matrix vector product es_ES
dc.subject GPU es_ES
dc.subject Multi-core es_ES
dc.subject Computed tomography es_ES
dc.subject.classification CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title A fast sparse block circulant matrix vector product es_ES
dc.type Capítulo de libro es_ES
dc.type Comunicación en congreso es_ES
dc.identifier.doi 10.1007/978-3-319-09873-9_46
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Instituto de Instrumentación para Imagen Molecular - Institut d'Instrumentació per a Imatge Molecular es_ES
dc.contributor.affiliation Universitat Politècnica de València. Escola Tècnica Superior d'Enginyeria Informàtica es_ES
dc.contributor.affiliation Universitat Politècnica de València. Escuela Politécnica Superior de Gandia - Escola Politècnica Superior de Gandia es_ES
dc.description.bibliographicCitation Romero Alcalde, E.; Tomás Domínguez, AE.; Soriano Asensi, A.; Blanquer Espert, I. (2014). A fast sparse block circulant matrix vector product. En Euro-Par 2014 Parallel Processing. Springer. 548-559. doi:10.1007/978-3-319-09873-9_46 es_ES
dc.description.accrualMethod S es_ES
dc.relation.conferencename 20th International European Conference on Parallel and Distributed Computing (Euro-Par 2014) es_ES
dc.relation.conferencedate 2014-08-25 es_ES
dc.relation.conferenceplace Porto, Portugal es_ES
dc.relation.publisherversion https://doi.org/10.1007/978-3-319-09873-9_46 es_ES
dc.description.upvformatpinicio 548 es_ES
dc.description.upvformatpfin 559 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.relation.senia 269087 es_ES
dc.identifier.eissn 1611-3349
dc.relation.references Bian, J., Siewerdsen, J.H., Han, X., Sidky, E.Y., Prince, J.L., Pelizzari, C.A., Pal, X.: Evaluation of sparse-view reconstruction from flat-panel-detector cone-beam ct. Physics in Medicine and Biology 55, 6575–6599 (2010) es_ES
dc.relation.references Dalton, S., Bell, N.: CUSP: A C++ templated sparse matrix library version 0.4.0 (2014), http://cusplibrary.github.com/ es_ES
dc.relation.references Feldkamp, L., Davis, L., Kress, J.: Practical cone-beam algorithm. Journal of the Optical Society of America 1, 612–619 (1984) es_ES
dc.relation.references Ganine, V., Legrand, M., Michalska, H., Pierre, C.: A sparse preconditioned iterative method for vibration analysis of geometrically mistuned bladed disks. Computers & Structures 87(5-6), 342–354 (2009) es_ES
dc.relation.references Hara, A.K., Paden, R.G., Silva, A.C., Kujak, J.L., Lawder, H.J., Pavlicek, W.: Iterative reconstruction technique for reducing body radiation dose at CT: Feasibility study. American Journal of Roentgenology 193, 764–771 (2009) es_ES
dc.relation.references Heroux, M.A., Bartlett, R.A., Howle, V.E., Hoekstra, R.J., Hu, J.J., Kolda, T.G., Lehoucq, R.B., Long, K.R., Pawlowski, R.P., Phipps, E.T., Salinger, A.G., Thornquist, H.K., Tuminaro, R.S., Willenbring, J.M., Williams, A., Stanley, K.S.: An overview of the Trilinos project. ACM Trans. Math. Softw. 31(3), 397–423 (2005) es_ES
dc.relation.references Im, E.J., Yelick, K., Vuduc, R.: Sparsity: Optimization framework for sparse matrix kernels. International Journal of High Performance Computing Applications 18(1), 135–158 (2004) es_ES
dc.relation.references Jones, E., Oliphant, T., Peterson, P., et al.: SciPy: Open source scientific tools for Python (2001), http://www.scipy.org/ es_ES
dc.relation.references Kaveh, A., Rahami, H.: Block circulant matrices and applications in free vibration analysis of cyclically repetitive structures. Acta Mechanica 217(1-2), 51–62 (2011) es_ES
dc.relation.references Kourtis, K., Goumas, G., Koziris, N.: Optimizing sparse matrix-vector multiplication using index and value compression. In: Proceedings of the 5th Conference on Computing Frontiers, CF 2008, pp. 87–96. ACM, New York (2008) es_ES
dc.relation.references Krotkiewski, M., Dabrowski, M.: Parallel symmetric sparse matrix–vector product on scalar multi-core CPUs. Parallel Computing 36(4), 181–198 (2010) es_ES
dc.relation.references Lee, B., Vuduc, R., Demmel, J., Yelick, K.: Performance models for evaluation and automatic tuning of symmetric sparse matrix-vector multiply. In: International Conference on Parallel Processing, ICPP 2004, vol. 1, pp. 169–176 (2004) es_ES
dc.relation.references Leroux, J.D., Selivanov, V., Fontaine, R., Lecomte, R.: Accelerated iterative image reconstruction methods based on block-circulant system matrix derived from a cylindrical image representation. In: Nuclear Science Symposium Conference Record, NSS 2007, vol. 4, pp. 2764–2771. IEEE (2007) es_ES
dc.relation.references NVIDIA: CUSPARSE library (2014), https://developer.nvidia.com/cusparse es_ES
dc.relation.references Pan, X., Sidky, E.Y., Vannier, M.: Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? Inverse Problems 25, 123009 (2008) es_ES
dc.relation.references Rodríguez-Alvarez, M.J., Soriano, A., Iborra, A., Sánchez, F., González, A.J., Conde, P., Hernández, L., Moliner, L., Orero, A., Vidal, L.F., Benlloch, J.M.: Expectation maximization (EM) algorithms using polar symmetries for computed tomography CT image reconstruction. Computers in Biology and Medicine 43(8), 1053–1061 (2013) es_ES
dc.relation.references Sheep, L., Vardi, Y.: Maximum likelihood reconstruction for emmision tomography. IEEE Transactions on Medical Imaging 1, 113–122 (1982) es_ES
dc.relation.references Sidky, E.Y., Pan, X.: Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization. Physics in Medicine and Biology 53, 4777–4807 (2008) es_ES
dc.relation.references Soriano, A., Rodríguez-Alvarez, M.J., Iborra, A., Sánchez, F., Carles, M., Conde, P., González, A.J., Hernández, L., Moliner, L., Orero, A., Vidal, L.F., Benlloch, J.M.: EM tomographic image reconstruction using polar voxels. Journal of Instrumentation 8, C01004 (2013) es_ES
dc.relation.references Thibaudeau, C., Leroux, J.D., Pratte, J.F., Fontaine, R., Lecomte, R.: Cylindrical and spherical ray-tracing for ct iterative reconstruction. In: 2011 IEEE Nuclear Science Symposium and Medical Imaging Conference (NSS/MIC), pp. 4378–4381 (2011) es_ES
dc.relation.references Vuduc, R., Demmel, J.W., Yelick, K.A.: OSKI: A library of automatically tuned sparse matrix kernels. Journal of Physics: Conference Series 16(1), 521 (2005) es_ES
dc.relation.references Vuduc, R.W., Moon, H.-J.: Fast sparse matrix-vector multiplication by exploiting variable block structure. In: Yang, L.T., Rana, O.F., Di Martino, B., Dongarra, J. (eds.) HPCC 2005. LNCS, vol. 3726, pp. 807–816. Springer, Heidelberg (2005) es_ES
dc.relation.references Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., Demmel, J.: Optimization of sparse matrix-vector multiplication on emerging multicore platforms. Parallel Computing 35(3), 178–194 (2009) es_ES


This item appears in the following Collection(s)

Show simple item record