Sparsification of rectangular matrices (Q1264423): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1006/jsco.1998.0204 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/jsco.1998.0204 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1967540313 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1006/JSCO.1998.0204 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 16:58, 10 December 2024

scientific article
Language Label Description Also known as
English
Sparsification of rectangular matrices
scientific article

    Statements

    Sparsification of rectangular matrices (English)
    0 references
    0 references
    0 references
    4 March 1999
    0 references
    The central problem treated in this paper is to construct an invertible square matrix \(T\) such that \(TA\), where \(A \in R^{n,m}\), \(m>n\), contains as many zero entries as possible. Three important observations concerning the nature of the problem are presented. A combinatorial search method is proposed to find an optimal sparsification. The number of arithmetic operations is exponential in the worst case. The most important improvement to this method is the exploitation of block structure. The several new theoretical results about block decomposition, its recognizing and sparsification based on this block decomposition are achieved. An open problem is the question if sparsification is indeed NP-complete. The problem of sparsification is relevant in many areas of application. The two practical examples illustrate where sparsification can be useful.
    0 references
    rectangular matrices
    0 references
    combinatorial search method
    0 references
    optimal sparsification
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references