Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding Linearly Dependent Rows in a Large Matrix

  1. Jul 16, 2012 #1
    I have a large real symmetric square matrix (with millions of rows/columns). How can I identify the sets of rows that are linearly dependent?

    More generally, can I determine linear independence of rows with a continuous function where, say, the function is 1.0 for a row that is linearly independent and 0.0 when it is linearly dependent. I am interested in identifying rows that are almost linearly dependent. For example, say that due to round-off error rows A and B are identical in all columns except that they differ by 1 part per million in one column's entries.
     
  2. jcsd
  3. Jul 16, 2012 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    If your matrix with 1,000,000 rows is full, the answer is "with great difficulty", unless you have access to a world-class supercomputing facility.

    If the matrix is sparse, a good way would be to find the smallest eigenvalues or singular values. The corresponding vectors give you linear combinations that are "almost" linearly dependent.
     
  4. Jul 16, 2012 #3
    Thanks. I should have mentioned that it is a very sparse matrix. Most rows have just a handful of non-zero entries although a few rows are exceptionally dense. I have been using the Mahout's Singular Value Decomposition program http://mahout.apache.org to find the eigenvectors. This program rejects the near-zero eigenvalue (in its "cleaning" stage) but I will check it out to see what it can tell me about the linearly dependent rows.
     
  5. Jul 18, 2012 #4
    In response to the questions posted by Windowmaker - which I received notice of but cannot find within this thread: What are you doing with a matrix that big? Is it the first LA course?

    I am afraid that I have strayed far from my physics education. I have a collection of nearly 2 billion packets that transited the gateways connecting our corporate network to the Internet over a few days. These involve 2.4 million unique IP addresses. So I created a 2.4M by 2.4M matrix where the indices map to the IP addresses and the elements are the number of packets exchanged between them. Perhaps surprisingly you can find individual eigenvectors fairly quickly but finding all of them is not practical. The first few eigenvectors primarily involve sums and differences of the key nodes (in terms of numbers of IPs they are in contact with and the numbers of packets exchanged).

    The sorts of questions I hope the eigenvectors will answer are:
    1) Which are the principal nodes in the network?
    2) Given a node, which nodes are sending similar numbers of packets to the same other nodes? (For example, I have noticed similar network attacks emanating from multiple IPs and would like an algorithmic approach to identifying the clones/copy-cats.)
    3) Which nodes share a structural similarity? (For example, given the IP address of the DNS server can I figure out which one is the backup DNS server?)

    Note that the matrix elements are all integers; my comment about round-off error was really about minor differences in packets counts due to a) time-limited data sample, b) lost packets being resent, ...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding Linearly Dependent Rows in a Large Matrix
Loading...