Incomplete Cross Approximation in the Mosaic-Skeleton Method View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2000-06

AUTHORS

E. Tyrtyshnikov

ABSTRACT

The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size. More... »

PAGES

367-380

References to SciGraph publications

Journal

TITLE

Computing

ISSUE

4

VOLUME

64

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s006070070031

DOI

http://dx.doi.org/10.1007/s006070070031

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1023005333


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Numerical Mathematics", 
          "id": "https://www.grid.ac/institutes/grid.465296.a", 
          "name": [
            "Institute of Numerical Mathematics Russian Academy of Sciences Gubkina 8, Moscow 117333 Russia E-mail: tee@inm.ras.ru, RU"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tyrtyshnikov", 
        "givenName": "E.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01396324", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004208576", 
          "https://doi.org/10.1007/bf01396324"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0024-3795(96)00301-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006813948"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/cpa.3160440202", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007210197"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/cpa.3160440202", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007210197"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1099-1506(199707/08)4:4<273::aid-nla97>3.0.co;2-t", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012876561"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013624951", 
          "https://doi.org/10.1007/bf02575706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02575706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013624951", 
          "https://doi.org/10.1007/bf02575706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0010-4655(91)90151-a", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024962034"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-011-5412-3_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027406828", 
          "https://doi.org/10.1007/978-94-011-5412-3_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-011-5412-3_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027406828", 
          "https://doi.org/10.1007/978-94-011-5412-3_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-8176-8136-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031869324", 
          "https://doi.org/10.1007/978-0-8176-8136-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-8176-8136-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031869324", 
          "https://doi.org/10.1007/978-0-8176-8136-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-0348-5812-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032434985", 
          "https://doi.org/10.1007/978-3-0348-5812-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-0348-5812-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032434985", 
          "https://doi.org/10.1007/978-3-0348-5812-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0021-9991(85)90002-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032552752"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-62598-4_132", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038040634", 
          "https://doi.org/10.1007/3-540-62598-4_132"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1515/rnam.1992.7.4.325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051341452"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0613030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062850381"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0909051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062857186"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0915046", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062857653"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00021408", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085169737", 
          "https://doi.org/10.1007/pl00021408"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000-06", 
    "datePublishedReg": "2000-06-01", 
    "description": "The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s006070070031", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1356894", 
        "issn": [
          "1521-9615", 
          "1436-5057"
        ], 
        "name": "Computing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "64"
      }
    ], 
    "name": "Incomplete Cross Approximation in the Mosaic-Skeleton Method", 
    "pagination": "367-380", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6d9a6543f7c874fa75b1e5f96ef9337e15d7db7f699c6d958bc452cb5ce40b8f"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s006070070031"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023005333"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s006070070031", 
      "https://app.dimensions.ai/details/publication/pub.1023005333"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:08", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000512.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs006070070031"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s006070070031'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s006070070031'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s006070070031'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s006070070031'


 

This table displays all metadata directly associated to this object as RDF triples.

115 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s006070070031 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N7edcaad5290a4d67bfdb12603845fb03
4 schema:citation sg:pub.10.1007/3-540-62598-4_132
5 sg:pub.10.1007/978-0-8176-8136-4
6 sg:pub.10.1007/978-3-0348-5812-0
7 sg:pub.10.1007/978-94-011-5412-3_11
8 sg:pub.10.1007/bf01396324
9 sg:pub.10.1007/bf02575706
10 sg:pub.10.1007/pl00021408
11 https://doi.org/10.1002/(sici)1099-1506(199707/08)4:4<273::aid-nla97>3.0.co;2-t
12 https://doi.org/10.1002/cpa.3160440202
13 https://doi.org/10.1016/0010-4655(91)90151-a
14 https://doi.org/10.1016/0021-9991(85)90002-6
15 https://doi.org/10.1016/s0024-3795(96)00301-1
16 https://doi.org/10.1137/0613030
17 https://doi.org/10.1137/0909051
18 https://doi.org/10.1137/0915046
19 https://doi.org/10.1515/rnam.1992.7.4.325
20 schema:datePublished 2000-06
21 schema:datePublishedReg 2000-06-01
22 schema:description The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree true
26 schema:isPartOf N4cf6233e97c34fdab7dade383fe92b04
27 Nae6eb68ae6044c67abcf7fa3623f7d22
28 sg:journal.1356894
29 schema:name Incomplete Cross Approximation in the Mosaic-Skeleton Method
30 schema:pagination 367-380
31 schema:productId N1629dc3d8f6b4c0d8a5df1bb01efc4e5
32 N5a0bee316af448439bc5ff0b71c53dc3
33 N790fc5f0eb284b248a46eac9552773f9
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023005333
35 https://doi.org/10.1007/s006070070031
36 schema:sdDatePublished 2019-04-10T19:08
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N23be9b08e56b4e44b47c3b80bd766779
39 schema:url http://link.springer.com/10.1007%2Fs006070070031
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N0169feeeb04b40b9b43b1900fa614d5f schema:affiliation https://www.grid.ac/institutes/grid.465296.a
44 schema:familyName Tyrtyshnikov
45 schema:givenName E.
46 rdf:type schema:Person
47 N1629dc3d8f6b4c0d8a5df1bb01efc4e5 schema:name dimensions_id
48 schema:value pub.1023005333
49 rdf:type schema:PropertyValue
50 N23be9b08e56b4e44b47c3b80bd766779 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N4cf6233e97c34fdab7dade383fe92b04 schema:volumeNumber 64
53 rdf:type schema:PublicationVolume
54 N5a0bee316af448439bc5ff0b71c53dc3 schema:name doi
55 schema:value 10.1007/s006070070031
56 rdf:type schema:PropertyValue
57 N790fc5f0eb284b248a46eac9552773f9 schema:name readcube_id
58 schema:value 6d9a6543f7c874fa75b1e5f96ef9337e15d7db7f699c6d958bc452cb5ce40b8f
59 rdf:type schema:PropertyValue
60 N7edcaad5290a4d67bfdb12603845fb03 rdf:first N0169feeeb04b40b9b43b1900fa614d5f
61 rdf:rest rdf:nil
62 Nae6eb68ae6044c67abcf7fa3623f7d22 schema:issueNumber 4
63 rdf:type schema:PublicationIssue
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
68 schema:name Statistics
69 rdf:type schema:DefinedTerm
70 sg:journal.1356894 schema:issn 1436-5057
71 1521-9615
72 schema:name Computing
73 rdf:type schema:Periodical
74 sg:pub.10.1007/3-540-62598-4_132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038040634
75 https://doi.org/10.1007/3-540-62598-4_132
76 rdf:type schema:CreativeWork
77 sg:pub.10.1007/978-0-8176-8136-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031869324
78 https://doi.org/10.1007/978-0-8176-8136-4
79 rdf:type schema:CreativeWork
80 sg:pub.10.1007/978-3-0348-5812-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032434985
81 https://doi.org/10.1007/978-3-0348-5812-0
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/978-94-011-5412-3_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027406828
84 https://doi.org/10.1007/978-94-011-5412-3_11
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bf01396324 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004208576
87 https://doi.org/10.1007/bf01396324
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bf02575706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013624951
90 https://doi.org/10.1007/bf02575706
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/pl00021408 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085169737
93 https://doi.org/10.1007/pl00021408
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1002/(sici)1099-1506(199707/08)4:4<273::aid-nla97>3.0.co;2-t schema:sameAs https://app.dimensions.ai/details/publication/pub.1012876561
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1002/cpa.3160440202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007210197
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0010-4655(91)90151-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1024962034
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0021-9991(85)90002-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032552752
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/s0024-3795(96)00301-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006813948
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/0613030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850381
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1137/0909051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062857186
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/0915046 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062857653
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1515/rnam.1992.7.4.325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051341452
112 rdf:type schema:CreativeWork
113 https://www.grid.ac/institutes/grid.465296.a schema:alternateName Institute of Numerical Mathematics
114 schema:name Institute of Numerical Mathematics Russian Academy of Sciences Gubkina 8, Moscow 117333 Russia E-mail: tee@inm.ras.ru, RU
115 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...