Compression and compressed inversion of interaction data

Abstract

A compression technique compresses interaction data. A fast method processes the compressed data without the need to first decompress the data. In one embodiment, the compression technique is used to compress data in an interaction matrix. The interaction matrix (such as a moment method impedance matrix) contains interaction data between sources (e.g., basis functions or expansion functions) and testers (e.g., testing functions). The sources are collected into groups of sources according to specified criteria. One useful criteria is based on grouping sources relatively close to one another. For each group of sources, a composite source is calculated. The testers are also collected into groups and composite testers are calculated. The use of composite sources and composite testers to compute couplings when the source and tester are not close to each other allows the interaction matrix to be computed as a sparse matrix with a block format.

1 . A method, comprising: 
 identifying first interaction data between a plurality of first sources and a plurality of first testers;    computing at least one composite source from one or more of said first sources;    computing at least one composite tester from one or more of said first testers;    transforming said first interaction data to second interaction data comprising said at least one composite source and further comprising said at least one composite tester, wherein said second interaction data comprises N sources and M testers;    identifying P sources out of said N sources;    identifying Q testers out of said M testers, wherein P and Q are greater than zero and either P is substantially less than N or Q is substantially less than M; and    applying a matrix transform to produce third interaction data from said second interaction data, wherein said third interaction data comprises relatively fewer interaction values than said second interaction data, and wherein the effect of any of said Q testers in exciting any of said P sources can be computed, at least in part, using said third interaction data.    
   
   
       2 . The method of  claim 1 , wherein said third interaction data is in the form of a product comprising a substantially lower triangular matrix and a substantially upper triangular matrix.  
   
   
       3 . The method of  claim 2 , further comprising the step of computing the excitation of said P sources by at least one of said Q testers.  
   
   
       4 . The method of  claim 1 , further comprising computing a factorization of said second interaction data wherein said factorization comprises a matrix with a significant triangular structure and using only a portion of said matrix with significant triangular structure to produce said third interaction data.  
   
   
       5 . The method of  claim 4 , further comprising the step of computing the excitation of said P sources by at least one of said Q testers.  
   
   
       6 . The method of  claim 1 , wherein said at least one composite tester comprises one or more composite testers that receive weakly from distant sources.  
   
   
       7 . The method of  claim 6 , further comprising the step of computing the excitation of said P sources by at least one of said Q testers.  
   
   
       8 . The method of  claim 6 , wherein said at least one composite source comprises one or more composite sources that broadcast weakly to distant locations.  
   
   
       9 . The method of  claim 8 , further comprising the step of computing the excitation of said P sources by at least one of said Q testers.  
   
   
       10 . The method of  claim 1 , wherein said at least one composite tester comprises one or more composite testers testing a localized excitation.  
   
   
       11 . The method of  claim 10 , further comprising the step of computing the excitation of said P sources by at least one of said Q testers.  
   
   
       12 . The method of  claim 1 , further comprising computing an LU factorization of said second interaction data and using only the bottom right portion of said LU factorization to produce said third interaction data.  
   
   
       13 . The method of  claim 12 , further comprising the step of computing the excitation of said P sources for an excitation wherein a number of said N sources describing said excitation have a strength that based on a desired accuracy may be approximated by zero.  
   
   
       14 . A method of data compression for a first system of linear equations comprising: 
 computing two or more composite basis functions from two or more original basis functions in said first system of linear equations;    computing two or more composite testing functions from two or more original testing functions in said first system of linear equations; and    transforming at least a portion of said first system of linear equations to a second system of linear equations using a second set of basis functions and a second set of testing functions, wherein said second set of basis functions comprises said two or more composite basis functions and said second set of testing functions comprises said two or more composite testing functions, wherein based on a desired accuracy relatively more elements of said second system of equations than elements of said first system of linear equations may be approximated by zero, and wherein at least one of said composite basis functions is spatially relatively close to at least one of said composite testers.    
   
   
       15 . The method of  claim 14  further comprising: 
 transforming an excitation described by said original testing functions into an excitation described by said second set of testing functions;    using said second system of equations and said excitation as described by said second set of testing functions computing the associated source as described by said second set of basis functions; and    transforming said source described by said basis functions from said second set of basis functions into a source described by said original basis functions.    
   
   
       16 . A method of data compression for a first interaction data based on a set of basis functions, comprising: 
 identifying a matrix of transmitted disturbances comprising transmitted disturbances for a plurality of spherical angles for said set of basis functions;    reducing a rank of said matrix of transmitted disturbances to yield a set of composite basis functions; and    transforming said first matrix of interaction data to yield a second matrix of interaction data comprising data for said set of composite basis functions, wherein based on a desired accuracy relatively more elements of said second matrix of interaction data may be approximated by zero than of said first matrix of interaction data, and wherein said first matrix of interaction data is not entirely contained within said matrix of transmitted disturbances.    
   
   
       17 . A method of data compression for a first interaction data based on a set of basis functions, comprising: 
 identifying a matrix of transmitted disturbances comprising transmitted disturbances for a plurality of spherical angles for said set of basis functions;    reducing a rank of said matrix of transmitted disturbances to yield a set of composite basis functions;    identifying a matrix of received disturbances comprising received disturbances for a plurality of spherical angles for said set of testing functions;    reducing a rank of said matrix of transmitted disturbances to yield a set of composite testing functions;    transforming said first matrix of interaction data to yield a second matrix of interaction data comprising data for said set of composite basis functions and said set of composite testing functions, wherein based on a desired accuracy relatively more elements of said second matrix of interaction data may be approximated by zero than of said first matrix of interaction data; and    further wherein said first matrix of interaction data is not entirely contained within one of said matrix of transmitted disturbances and said matrix of received disturbances.    
   
   
       18 . The method of  claim 17 , wherein said first matrix of interaction data is not entirely contained within said matrix of transmitted disturbances and said first matrix of interaction data is not entirely contained within said matrix of received disturbances.