An algorithm for the fast solution of symmetric linear complementarity problems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-12

AUTHORS

José Luis Morales, Jorge Nocedal, Mikhail Smelyanskiy

ABSTRACT

This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95–106, 1994) that combines projected Gauss–Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios. More... »

PAGES

251-266

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00211-008-0183-5

DOI

http://dx.doi.org/10.1007/s00211-008-0183-5

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "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": "Instituto Tecnol\u00f3gico Aut\u00f3nomo de M\u00e9xico", 
          "id": "https://www.grid.ac/institutes/grid.454349.b", 
          "name": [
            "Departamento de Matem\u00e1ticas, Instituto Tecnol\u00f3gico Aut\u00f3nomo de M\u00e9xico, Mexico City, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Morales", 
        "givenName": "Jos\u00e9 Luis", 
        "id": "sg:person.013407611707.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013407611707.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Northwestern University", 
          "id": "https://www.grid.ac/institutes/grid.16753.36", 
          "name": [
            "Department of Electrical Engineering and Computer Science, Northwestern University, Chicago, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nocedal", 
        "givenName": "Jorge", 
        "id": "sg:person.01157306714.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01157306714.71"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Intel (United States)", 
          "id": "https://www.grid.ac/institutes/grid.419318.6", 
          "name": [
            "The Intel Corporation, Santa Clara, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Smelyanskiy", 
        "givenName": "Mikhail", 
        "id": "sg:person.01356341566.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356341566.92"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1003120642", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-12211-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003120642", 
          "https://doi.org/10.1007/978-3-662-12211-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-12211-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003120642", 
          "https://doi.org/10.1007/978-3-662-12211-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.future.2003.07.011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004320133"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/279232.279236", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006445520"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1250662.1250683", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011373650"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1008292328909", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016244262", 
          "https://doi.org/10.1023/a:1008292328909"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/502800.502803", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017283608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0024-3795(68)90052-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021814305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00211-004-0569-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026272611", 
          "https://doi.org/10.1007/s00211-004-0569-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00211-004-0569-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026272611", 
          "https://doi.org/10.1007/s00211-004-0569-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0024-3795(80)90173-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026892084"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002110050050", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034738342", 
          "https://doi.org/10.1007/s002110050050"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1362622.1362652", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048238801"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1019928808826", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050018480", 
          "https://doi.org/10.1023/a:1019928808826"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ro:2007009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1057066066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0320018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062843621"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/050635225", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062846363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0725029", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062853348"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0725068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062853387"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0801008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062854121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0036144595285963", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062877884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1052623497330963", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883648"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1052623498345075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883692"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611971453", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098555847"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008-12", 
    "datePublishedReg": "2008-12-01", 
    "description": "This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95\u2013106, 1994) that combines projected Gauss\u2013Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00211-008-0183-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136759", 
        "issn": [
          "0029-599X", 
          "0945-3245"
        ], 
        "name": "Numerische Mathematik", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "111"
      }
    ], 
    "name": "An algorithm for the fast solution of symmetric linear complementarity problems", 
    "pagination": "251-266", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "09357d28562f4b37876c65bd8977d6ae246928a816f27551b428fb0186b2d05b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00211-008-0183-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001933348"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00211-008-0183-5", 
      "https://app.dimensions.ai/details/publication/pub.1001933348"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:30", 
    "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/0000000373_0000000373/records_13090_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00211-008-0183-5"
  }
]
 

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/s00211-008-0183-5'

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/s00211-008-0183-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00211-008-0183-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00211-008-0183-5'


 

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

154 TRIPLES      21 PREDICATES      50 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00211-008-0183-5 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N29123ef41d2e433cb6299250ab59ba89
4 schema:citation sg:pub.10.1007/978-3-662-12211-2
5 sg:pub.10.1007/s00211-004-0569-y
6 sg:pub.10.1007/s002110050050
7 sg:pub.10.1023/a:1008292328909
8 sg:pub.10.1023/a:1019928808826
9 https://app.dimensions.ai/details/publication/pub.1003120642
10 https://doi.org/10.1016/0024-3795(68)90052-9
11 https://doi.org/10.1016/0024-3795(80)90173-1
12 https://doi.org/10.1016/j.future.2003.07.011
13 https://doi.org/10.1051/ro:2007009
14 https://doi.org/10.1137/0320018
15 https://doi.org/10.1137/050635225
16 https://doi.org/10.1137/0725029
17 https://doi.org/10.1137/0725068
18 https://doi.org/10.1137/0801008
19 https://doi.org/10.1137/1.9781611971453
20 https://doi.org/10.1137/s0036144595285963
21 https://doi.org/10.1137/s1052623497330963
22 https://doi.org/10.1137/s1052623498345075
23 https://doi.org/10.1145/1250662.1250683
24 https://doi.org/10.1145/1362622.1362652
25 https://doi.org/10.1145/279232.279236
26 https://doi.org/10.1145/502800.502803
27 schema:datePublished 2008-12
28 schema:datePublishedReg 2008-12-01
29 schema:description This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95–106, 1994) that combines projected Gauss–Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios.
30 schema:genre research_article
31 schema:inLanguage en
32 schema:isAccessibleForFree true
33 schema:isPartOf N14a1beef786647c49eacb0774d8afaaf
34 Ne98c969f97a84993bb266981e835fc1e
35 sg:journal.1136759
36 schema:name An algorithm for the fast solution of symmetric linear complementarity problems
37 schema:pagination 251-266
38 schema:productId N4ce15fc618e14164b62e96baa9f6bdd9
39 N90505385d07d43219b0c299bd3df08b0
40 Nce8ab887bba1468a9a364e0fd1604fc9
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001933348
42 https://doi.org/10.1007/s00211-008-0183-5
43 schema:sdDatePublished 2019-04-11T14:30
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N77f4311eb18b43668565f53d9e1125d9
46 schema:url http://link.springer.com/10.1007/s00211-008-0183-5
47 sgo:license sg:explorer/license/
48 sgo:sdDataset articles
49 rdf:type schema:ScholarlyArticle
50 N14a1beef786647c49eacb0774d8afaaf schema:issueNumber 2
51 rdf:type schema:PublicationIssue
52 N14fdb18d3f33464bb100a2559da3a788 rdf:first sg:person.01157306714.71
53 rdf:rest Nd5c6d81871ed4719b1b8447671a6198e
54 N29123ef41d2e433cb6299250ab59ba89 rdf:first sg:person.013407611707.52
55 rdf:rest N14fdb18d3f33464bb100a2559da3a788
56 N4ce15fc618e14164b62e96baa9f6bdd9 schema:name readcube_id
57 schema:value 09357d28562f4b37876c65bd8977d6ae246928a816f27551b428fb0186b2d05b
58 rdf:type schema:PropertyValue
59 N77f4311eb18b43668565f53d9e1125d9 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N90505385d07d43219b0c299bd3df08b0 schema:name doi
62 schema:value 10.1007/s00211-008-0183-5
63 rdf:type schema:PropertyValue
64 Nce8ab887bba1468a9a364e0fd1604fc9 schema:name dimensions_id
65 schema:value pub.1001933348
66 rdf:type schema:PropertyValue
67 Nd5c6d81871ed4719b1b8447671a6198e rdf:first sg:person.01356341566.92
68 rdf:rest rdf:nil
69 Ne98c969f97a84993bb266981e835fc1e schema:volumeNumber 111
70 rdf:type schema:PublicationVolume
71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
72 schema:name Mathematical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
75 schema:name Numerical and Computational Mathematics
76 rdf:type schema:DefinedTerm
77 sg:journal.1136759 schema:issn 0029-599X
78 0945-3245
79 schema:name Numerische Mathematik
80 rdf:type schema:Periodical
81 sg:person.01157306714.71 schema:affiliation https://www.grid.ac/institutes/grid.16753.36
82 schema:familyName Nocedal
83 schema:givenName Jorge
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01157306714.71
85 rdf:type schema:Person
86 sg:person.013407611707.52 schema:affiliation https://www.grid.ac/institutes/grid.454349.b
87 schema:familyName Morales
88 schema:givenName José Luis
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013407611707.52
90 rdf:type schema:Person
91 sg:person.01356341566.92 schema:affiliation https://www.grid.ac/institutes/grid.419318.6
92 schema:familyName Smelyanskiy
93 schema:givenName Mikhail
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356341566.92
95 rdf:type schema:Person
96 sg:pub.10.1007/978-3-662-12211-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003120642
97 https://doi.org/10.1007/978-3-662-12211-2
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/s00211-004-0569-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1026272611
100 https://doi.org/10.1007/s00211-004-0569-y
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s002110050050 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034738342
103 https://doi.org/10.1007/s002110050050
104 rdf:type schema:CreativeWork
105 sg:pub.10.1023/a:1008292328909 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016244262
106 https://doi.org/10.1023/a:1008292328909
107 rdf:type schema:CreativeWork
108 sg:pub.10.1023/a:1019928808826 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050018480
109 https://doi.org/10.1023/a:1019928808826
110 rdf:type schema:CreativeWork
111 https://app.dimensions.ai/details/publication/pub.1003120642 schema:CreativeWork
112 https://doi.org/10.1016/0024-3795(68)90052-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021814305
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0024-3795(80)90173-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026892084
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/j.future.2003.07.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004320133
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1051/ro:2007009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057066066
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/0320018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062843621
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/050635225 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062846363
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/0725029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062853348
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/0725068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062853387
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1137/0801008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854121
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1137/1.9781611971453 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098555847
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1137/s0036144595285963 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062877884
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1137/s1052623497330963 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883648
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1137/s1052623498345075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883692
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/1250662.1250683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011373650
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1145/1362622.1362652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048238801
141 rdf:type schema:CreativeWork
142 https://doi.org/10.1145/279232.279236 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006445520
143 rdf:type schema:CreativeWork
144 https://doi.org/10.1145/502800.502803 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017283608
145 rdf:type schema:CreativeWork
146 https://www.grid.ac/institutes/grid.16753.36 schema:alternateName Northwestern University
147 schema:name Department of Electrical Engineering and Computer Science, Northwestern University, Chicago, USA
148 rdf:type schema:Organization
149 https://www.grid.ac/institutes/grid.419318.6 schema:alternateName Intel (United States)
150 schema:name The Intel Corporation, Santa Clara, CA, USA
151 rdf:type schema:Organization
152 https://www.grid.ac/institutes/grid.454349.b schema:alternateName Instituto Tecnológico Autónomo de México
153 schema:name Departamento de Matemáticas, Instituto Tecnológico Autónomo de México, Mexico City, Mexico
154 rdf:type schema:Organization
 




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


...