Please use this identifier to cite or link to this item: http://ktisis.cut.ac.cy/handle/10488/6767
Title: Algorithms for computing the qr decomposition of a set of matrices with common columns
Authors: Yanev, Petko I. 
Foschi, Paolo 
Kontoghiorghes, Erricos John 
Keywords: Computational complexity
Mathematical models
Algorithms
Issue Date: 2004
Publisher: Springer Link
Source: Algorithmica (New York), 2004, Volume 39, Issue 1,Pages 83-93
Abstract: The QR decomposition of a set of matrices which have common columns is investigated. The triangular factors of the QR decompositions are represented as nodes of a weighted directed graph. An edge between two nodes exists if and only if the columns of one of the matrices is a subset of the columns of the other. The weight of an edge denotes the computational complexity of deriving the triangular factor of the destination node from that of the source node. The problem is equivalent to constructing the graph and finding the minimum cost for visiting all the nodes. An algorithm which computes the QR decompositions by deriving the minimum spanning tree of the graph is proposed. Theoretical measures of complexity are derived and numerical results from the implementation of this and alternative heuristic algorithms are given.
URI: http://ktisis.cut.ac.cy/handle/10488/6767
ISSN: 0178-4617 (print)
1432-0541 (online)
DOI: 10.1007/s00453-003-1080-z
Rights: © 2004 Springer-Verlag New York Inc.
Appears in Collections:Άρθρα/Articles

Show full item record

SCOPUSTM   
Citations 20

8
checked on Dec 16, 2016

WEB OF SCIENCETM
Citations 20

8
checked on May 16, 2017

Page view(s)

11
Last Week
2
Last month
checked on May 26, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.