A fast algorithm for determining the primitivity of an n x n nonnegative matrix Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/ff365753t

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Nonnegative matrices have a myriad of applications in the biological, social, and physical genres. Of particular importance are the primitive matrices. A nonnegative matrix, M, is primitive exactly when there is a positive integer, k, such that M[superscript k] has only positive entries; that is, all the entries in M[superscript k] are strictly greater than zero. This method of determining if a matrix is primitive uses matrix multiplication and so would require time Ω(n[superscipt α]) where α>2.3 even if fast matrix multiplication were used. Our goal is to find a much faster algorithm. This can be achieved by viewing a nonnegative matrix, M, as the adjacency matrix for a graph, G(M). The matrix, M, is primitive if and only if G(M) is strongly connected and the greatest common divisor of the cycle lengths in G(M) is 1. We devised an algorithm based in breadth-first search which finds a set of cycle lengths whose gcd is the same as that of G(M). This algorithm has runtime O(e) where e is the number of nonzero entries in M and therefore equivalent to the number of edges in G(M). A proof is given shown the runtime of O(n + e) along with some empirical evidence that supports this finding.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2012-07-18T22:09:48Z No. of bitstreams: 1 LeegardAmandaD2003.pdf: 622784 bytes, checksum: b725e03ab2707dd845e9b6d154aefc7e (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-07-26T17:17:08Z (GMT) No. of bitstreams: 1 LeegardAmandaD2003.pdf: 622784 bytes, checksum: b725e03ab2707dd845e9b6d154aefc7e (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-07-26T17:21:31Z (GMT) No. of bitstreams: 1 LeegardAmandaD2003.pdf: 622784 bytes, checksum: b725e03ab2707dd845e9b6d154aefc7e (MD5)
  • description.provenance : Made available in DSpace on 2012-07-26T17:21:31Z (GMT). No. of bitstreams: 1 LeegardAmandaD2003.pdf: 622784 bytes, checksum: b725e03ab2707dd845e9b6d154aefc7e (MD5) Previous issue date: 2002-11-27

Relationships

In Administrative Set:
Last modified: 08/03/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items