Mosaic-Skeleton approximations View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1996-06

AUTHORS

Eugene Tyrtyshnikov

ABSTRACT

If a matrix has a small rank then it can be multiplied by a vector with many savings in memory and arithmetic. As was recently shown by the author, the same applies to the matrices which might be of full classical rank but have a smallmosaic rank. The mosaic-skeleton approximations seem to have imposing applications to the solution of large dense unstructured linear systems. In this paper, we propose a suitable modification of brandt's definition of an asymptotically smooth functionf(x,y). Then we considern×n matricesAn=[f(xi(n),yj(n))] for quasiuniform meshes {xi(n)} and {yj(n)} in some bounded domain in them-dimensional space. For such matrices, we prove that the approximate mosaic ranks grow logarithmically inn. From practical point of view, the results obtained lead immediately toO(n logn) matrix-vector multiplication algorithms. More... »

PAGES

47-57

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Russian Academy of Sciences", 
          "id": "https://www.grid.ac/institutes/grid.4886.2", 
          "name": [
            "Institute of Numerical Mathematics, Russian Academy of Sciences, Gubkina 8, 117333, Moscow, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tyrtyshnikov", 
        "givenName": "Eugene", 
        "id": "sg:person.014057406623.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014057406623.21"
        ], 
        "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/0010-4655(91)90151-a", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024962034"
        ], 
        "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": "https://doi.org/10.1515/rnam.1992.7.4.325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051341452"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996-06", 
    "datePublishedReg": "1996-06-01", 
    "description": "If a matrix has a small rank then it can be multiplied by a vector with many savings in memory and arithmetic. As was recently shown by the author, the same applies to the matrices which might be of full classical rank but have a smallmosaic rank. The mosaic-skeleton approximations seem to have imposing applications to the solution of large dense unstructured linear systems. In this paper, we propose a suitable modification of brandt's definition of an asymptotically smooth functionf(x,y). Then we considern\u00d7n matricesAn=[f(xi(n),yj(n))] for quasiuniform meshes {xi(n)} and {yj(n)} in some bounded domain in them-dimensional space. For such matrices, we prove that the approximate mosaic ranks grow logarithmically inn. From practical point of view, the results obtained lead immediately toO(n logn) matrix-vector multiplication algorithms.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02575706", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1135974", 
        "issn": [
          "0008-0624", 
          "1126-5434"
        ], 
        "name": "Calcolo", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "name": "Mosaic-Skeleton approximations", 
    "pagination": "47-57", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "40e813a4ce86ec93ce3f5aaeb7c953211bcb858ba80d1c9a58c2e47a6c66d679"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02575706"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013624951"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02575706", 
      "https://app.dimensions.ai/details/publication/pub.1013624951"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:32", 
    "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/0000000370_0000000370/records_46765_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02575706"
  }
]
 

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/bf02575706'

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/bf02575706'

Turtle is a human-readable linked data format.

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

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

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


 

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

74 TRIPLES      21 PREDICATES      31 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02575706 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nb45f000b23e147e4a390d1e49771cdc0
4 schema:citation sg:pub.10.1007/bf01396324
5 https://doi.org/10.1016/0010-4655(91)90151-a
6 https://doi.org/10.1016/0021-9991(85)90002-6
7 https://doi.org/10.1515/rnam.1992.7.4.325
8 schema:datePublished 1996-06
9 schema:datePublishedReg 1996-06-01
10 schema:description If a matrix has a small rank then it can be multiplied by a vector with many savings in memory and arithmetic. As was recently shown by the author, the same applies to the matrices which might be of full classical rank but have a smallmosaic rank. The mosaic-skeleton approximations seem to have imposing applications to the solution of large dense unstructured linear systems. In this paper, we propose a suitable modification of brandt's definition of an asymptotically smooth functionf(x,y). Then we considern×n matricesAn=[f(xi(n),yj(n))] for quasiuniform meshes {xi(n)} and {yj(n)} in some bounded domain in them-dimensional space. For such matrices, we prove that the approximate mosaic ranks grow logarithmically inn. From practical point of view, the results obtained lead immediately toO(n logn) matrix-vector multiplication algorithms.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf Na20127fb06434d76913b5484e87daa58
15 Nc36d760f3d7c476c887f167f6fab6970
16 sg:journal.1135974
17 schema:name Mosaic-Skeleton approximations
18 schema:pagination 47-57
19 schema:productId Na4a9d50a9cef4f8f9b8b6d07e9da516d
20 Nd8fae4279c8f4dd9bb1c70ae062ae93a
21 Nfd92e25aa0ab4437a475c65fb273b2ae
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013624951
23 https://doi.org/10.1007/bf02575706
24 schema:sdDatePublished 2019-04-11T13:32
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N7218c51e809a49b2a6bf4cfdd67e3c90
27 schema:url http://link.springer.com/10.1007%2FBF02575706
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N7218c51e809a49b2a6bf4cfdd67e3c90 schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 Na20127fb06434d76913b5484e87daa58 schema:volumeNumber 33
34 rdf:type schema:PublicationVolume
35 Na4a9d50a9cef4f8f9b8b6d07e9da516d schema:name readcube_id
36 schema:value 40e813a4ce86ec93ce3f5aaeb7c953211bcb858ba80d1c9a58c2e47a6c66d679
37 rdf:type schema:PropertyValue
38 Nb45f000b23e147e4a390d1e49771cdc0 rdf:first sg:person.014057406623.21
39 rdf:rest rdf:nil
40 Nc36d760f3d7c476c887f167f6fab6970 schema:issueNumber 1-2
41 rdf:type schema:PublicationIssue
42 Nd8fae4279c8f4dd9bb1c70ae062ae93a schema:name dimensions_id
43 schema:value pub.1013624951
44 rdf:type schema:PropertyValue
45 Nfd92e25aa0ab4437a475c65fb273b2ae schema:name doi
46 schema:value 10.1007/bf02575706
47 rdf:type schema:PropertyValue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
52 schema:name Artificial Intelligence and Image Processing
53 rdf:type schema:DefinedTerm
54 sg:journal.1135974 schema:issn 0008-0624
55 1126-5434
56 schema:name Calcolo
57 rdf:type schema:Periodical
58 sg:person.014057406623.21 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
59 schema:familyName Tyrtyshnikov
60 schema:givenName Eugene
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014057406623.21
62 rdf:type schema:Person
63 sg:pub.10.1007/bf01396324 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004208576
64 https://doi.org/10.1007/bf01396324
65 rdf:type schema:CreativeWork
66 https://doi.org/10.1016/0010-4655(91)90151-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1024962034
67 rdf:type schema:CreativeWork
68 https://doi.org/10.1016/0021-9991(85)90002-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032552752
69 rdf:type schema:CreativeWork
70 https://doi.org/10.1515/rnam.1992.7.4.325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051341452
71 rdf:type schema:CreativeWork
72 https://www.grid.ac/institutes/grid.4886.2 schema:alternateName Russian Academy of Sciences
73 schema:name Institute of Numerical Mathematics, Russian Academy of Sciences, Gubkina 8, 117333, Moscow, Russia
74 rdf:type schema:Organization
 




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


...