- -

A multicore solution to Block-Toeplitz linear systems of equations

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A multicore solution to Block-Toeplitz linear systems of equations

Show simple item record

Files in this item

dc.contributor.author Alonso-Jordá, Pedro es_ES
dc.contributor.author Argüelles, Daniel es_ES
dc.contributor.author Ranilla, José es_ES
dc.contributor.author Vidal Maciá, Antonio Manuel es_ES
dc.date.accessioned 2014-09-16T07:33:42Z
dc.date.issued 2013-09
dc.identifier.issn 0920-8542
dc.identifier.uri http://hdl.handle.net/10251/39670
dc.description.abstract There exist algorithms, also called "fast" algorithms, which exploit the special structure of Toeplitz matrices so that, e.g., allow to solve a linear system of equations in O(n2) flops. However, some implementations of classical algorithms that do not use this structure (O(n3) flops) highly reduce the time to solution when several cores are available. That is why it is necessary to work on "fast" algorithms so that they do not lose track of the benefits of new hardware/software. In this work, we propose a new approach to the Generalized Schur Algorithm, a very known al- gorithm for the solution of Toeplitz systems, to work on a Block-Toeplitz matrix. Our algorithm is based on matrix-matrix multiplications, thus allowing to exploit an efficient implementation of this operation if it exists. Our algorithm also makes use of the thread level parallelism featured by multicores to decrease execution time. es_ES
dc.description.sponsorship PROMETEO/2009/013, Generalitat Valenciana. Projects TEC2009-13741, TIN2010-14971 and TIN2011-15734-E of the Ministerio Espanol de Ciencia e Innovacion, and TEC2012-38142-C04 of the Ministerio Espanol de Economia y Competitividad. en_EN
dc.language Inglés es_ES
dc.publisher Springer Verlag (Germany) es_ES
dc.relation.ispartof Journal of Supercomputing es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Block-Toeplitz es_ES
dc.subject Linear systems es_ES
dc.subject Generalized Schur Algorithm es_ES
dc.subject Multicore-computers 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 multicore solution to Block-Toeplitz linear systems of equations es_ES
dc.type Artículo es_ES
dc.embargo.lift 10000-01-01
dc.identifier.doi 10.1007/s11227-012-0824-4
dc.relation.projectID info:eu-repo/grantAgreement/Generalitat Valenciana//PROMETEO09%2F2009%2F013/ES/Computacion de altas prestaciones sobre arquitecturas actuales en porblemas de procesado múltiple de señal/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//TEC2012-38142-C04-01/ES/PROCESADO DISTRIBUIDO Y COLABORATIVO DE SEÑALES SONORAS: CONTROL ACTIVO/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//TEC2009-13741/ES/Spatial Audio Systems Based On Massive Parallel Processing Of Multichannel Acoustic Signals With General Purpose-Graphics Processing Units (Gp-Gpu) And Multicores/ / es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//TEC2012-38142-C04-04/ES/PROCESADO DISTRIBUIDO Y COLABORATIVO DE SEÑALES SONORAS: COMPUTACION DISTRIBUIDA/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//TIN2010-14971/ES/REDUCCION DE CARACTERISTICAS Y COMPUTACION DE ALTAS PRESTACIONES EN PROBLEMAS DE ALTA DIMENSIONALIDAD/ / es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//TIN2011-15734-E/ES/RED DE COMPUTACION DE ALTAS PRESTACIONES SOBRE ARQUITECTURAS PARALELAS HETEROGENEAS (CAPAP-H4) RENOVACION/ es_ES
dc.rights.accessRights Cerrado es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Alonso-Jordá, P.; Argüelles, D.; Ranilla, J.; Vidal Maciá, AM. (2013). A multicore solution to Block-Toeplitz linear systems of equations. Journal of Supercomputing. 65(3):999-1009. https://doi.org/10.1007/s11227-012-0824-4 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://link.springer.com/article/10.1007%2Fs11227-012-0824-4 es_ES
dc.description.upvformatpinicio 999 es_ES
dc.description.upvformatpfin 1009 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 65 es_ES
dc.description.issue 3 es_ES
dc.relation.senia 232744
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.description.references Alonso P, Badía JM, Vidal AM (2005) An efficient parallel algorithm to solve block–Toeplitz systems. J Supercomput 32:251–278 es_ES
dc.description.references Alonso P, Argüeso F, Cortina R, Ranilla J, Vidal AM Non-linear parallel solver for detecting point sources in CMB maps using Bayesian techniques. J Math Chem. doi: 10.1007/s10910-012-0078-7 es_ES
dc.description.references Anderson E et al (1999) LAPACK users’ guide, 3rd edn. SIAM, Philadelphia es_ES
dc.description.references Bischof C, van Loan C (1987) The WY representation for products of householder matrices. SIAM J Sci Stat Comput 8(1):2–13 es_ES
dc.description.references Chun J, Kailath T, Lev-Ari H (1987) Fast parallel algorithms for QR and triangular factorization. SIAM J Sci Stat Comput 8(6):899–913 es_ES
dc.description.references Cybenko G, Berry M (1990) Hyperbolic householder algorithms for factoring structured matrices. SIAM J Matrix Anal Appl 11(4):499–520 es_ES
dc.description.references Gallivan K, Thirumalai S, Van Dooren P (1994) On solving block Toeplitz systems using a block Schur algorithm. In: Proceedings of the 23rd international conference on parallel processing, vol 3. CRC Press, Boca Raton, pp 274–281 es_ES
dc.description.references Gustavson FG (1997) Recursion leads to automatic variable blocking for dense linear-algebra algorithms. IBM J Res Dev 41(6):737–755 es_ES
dc.description.references Intel MKL (2012) http://software.intel.com/en-us/articles/intel-mkl es_ES
dc.description.references Jin XQ (2002) Developments and applications of Block Toeplitz iterative solvers. Combinatorics and computer science. Science Press, Beijing es_ES
dc.description.references Kailath T, Sayed AH (1995) Displacement structure: theory and applications. SIAM Rev 37(3):297–386 es_ES
dc.description.references PLASMA Project (2012) The parallel linear algebra for scalable multi-core architectures. http://icl.cs.utk.edu/plasma es_ES
dc.description.references StructPack (2012) A high performance computing library for structured matrices. http://www.inco2.upv.es/structpack.html es_ES


This item appears in the following Collection(s)

Show simple item record