Hierarchical matrix

<p>In <a href="/facts/Numerical_mathematics/QT9cYa9z">numerical mathematics</a>, hierarchical matrices (H-matrices)
are used as data-sparse approximations of non-sparse matrices. While a <a href="/facts/Sparse_matrix/FFtN0XjR">sparse matrix</a> of dimension 
  
    
      
        n
      
    
    {\displaystyle n}
  
 can be represented efficiently in 
  
    
      
        O
        (
        n
        )
      
    
    {\displaystyle O(n)}
  
 units of storage by storing only its non-zero entries, a non-sparse matrix would require 
  
    
      
        O
        (
        
          n
          
            2
          
        
        )
      
    
    {\displaystyle O(n^{2})}
  
 units of storage, and using this type of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time. Hierarchical matrices provide an approximation requiring only 
  
    
      
        O
        (
        n
        k
        
        log
        ⁡
        (
        n
        )
        )
      
    
    {\displaystyle O(nk\,\log(n))}
  
 units of storage, where 
  
    
      
        k
      
    
    {\displaystyle k}
  
 is a parameter controlling the accuracy of the approximation. In typical applications, e.g., when discretizing integral equations,
preconditioning the resulting systems of linear equations,
or solving elliptic partial differential equations, a rank proportional to 
  
    
      
        log
        ⁡
        (
        1
        
          /
        
        ϵ
        
          )
          
            γ
          
        
      
    
    {\displaystyle \log(1/\epsilon )^{\gamma }}
  
 with a small constant 
  
    
      
        γ
      
    
    {\displaystyle \gamma }
  
 is sufficient to ensure an accuracy of 
  
    
      
        ϵ
      
    
    {\displaystyle \epsilon }
  
. Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage: the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated in 
  
    
      
        O
        (
        n
        
          k
          
            α
          
        
        
        log
        ⁡
        (
        n
        
          )
          
            β
          
        
        )
      
    
    {\displaystyle O(nk^{\alpha }\,\log(n)^{\beta })}
  
 operations, where 
  
    
      
        α
        ,
        β
        ∈
        {
        1
        ,
        2
        ,
        3
        }
        .
      
    
    {\displaystyle \alpha ,\beta \in \{1,2,3\}.}

</p>

Hierarchical matrix open-in-new

Hierarchical matrix