Parallel computation of two-point boundary-value problems via particular solutions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-10

AUTHORS

A. Miele, T. Wang

ABSTRACT

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm−1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance. More... »

PAGES

5-29

References to SciGraph publications

  • 1992-06. Parallel solver for trajectory optimization search directions in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1968-07. Method of particular solutions for linear, two-point boundary-value problems in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1971-04. Multipoint solution of two-point boundary-value problems in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1980-01. Parallel algorithms for solving nonlinear two-point boundary-value problems which arise in optimal control in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1970-05. General technique for solving nonlinear, two-point boundary-value problems via the method of particular solutions in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Aero-Astronautics Group, Rice University, Houston, Texas", 
              "id": "http://www.grid.ac/institutes/grid.21940.3e", 
              "name": [
                "Aero-Astronautics Group, Rice University, Houston, Texas"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Miele", 
            "givenName": "A.", 
            "id": "sg:person.015552732657.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015552732657.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Aero-Astronautics Group, Rice University, Houston, Texas", 
              "id": "http://www.grid.ac/institutes/grid.21940.3e", 
              "name": [
                "Aero-Astronautics Group, Rice University, Houston, Texas"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "T.", 
            "id": "sg:person.014414570607.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014414570607.44"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf00937371", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008341596", 
              "https://doi.org/10.1007/bf00937371"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00934589", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036234620", 
              "https://doi.org/10.1007/bf00934589"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00940054", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007660607", 
              "https://doi.org/10.1007/bf00940054"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00928674", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018094581", 
              "https://doi.org/10.1007/bf00928674"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00928709", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052124489", 
              "https://doi.org/10.1007/bf00928709"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-10", 
        "datePublishedReg": "1993-10-01", 
        "description": "Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm\u22121 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf00941885", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1044187", 
            "issn": [
              "0022-3239", 
              "1573-2878"
            ], 
            "name": "Journal of Optimization Theory and Applications", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "79"
          }
        ], 
        "keywords": [
          "two-point boundary value problem", 
          "boundary value problem", 
          "linear algebraic system", 
          "vector of constants", 
          "particular solutions", 
          "algebraic system", 
          "differential systems", 
          "linear problem", 
          "large linear algebraic systems", 
          "trajectory optimization", 
          "real-time trajectory optimization", 
          "efficient solution", 
          "quasilinearization technique", 
          "two-point case", 
          "nonlinear problems", 
          "nonhomogeneous systems", 
          "different initial conditions", 
          "time subinterval", 
          "iterative solution", 
          "subsequent subintervals", 
          "state vector", 
          "computational effort", 
          "first subinterval", 
          "discrete version", 
          "numerical tests", 
          "initial conditions", 
          "linear transformation", 
          "continuity conditions", 
          "subintervals", 
          "parallel computation", 
          "parallel computers", 
          "decomposition technique", 
          "parallel algorithm", 
          "sequential algorithm", 
          "interface conditions", 
          "substantial speedup", 
          "state domain", 
          "multi-point approach", 
          "time domain", 
          "speedup", 
          "optimization", 
          "problem", 
          "solution", 
          "different processors", 
          "algorithm", 
          "present technique", 
          "vector", 
          "wheren", 
          "computation", 
          "system", 
          "constants", 
          "computer", 
          "technique", 
          "particular nature", 
          "same size", 
          "considerable interest", 
          "drawbacks", 
          "achievable", 
          "cases", 
          "dimensions", 
          "conditions", 
          "version", 
          "domain", 
          "parallelism", 
          "approach", 
          "processors", 
          "separate tasks", 
          "interest", 
          "transformation", 
          "size", 
          "task", 
          "means", 
          "implementation", 
          "MPS", 
          "features", 
          "nature", 
          "sequence", 
          "requirements", 
          "interface", 
          "intercommunication", 
          "efforts", 
          "guidance", 
          "key", 
          "test", 
          "method"
        ], 
        "name": "Parallel computation of two-point boundary-value problems via particular solutions", 
        "pagination": "5-29", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1008022091"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00941885"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00941885", 
          "https://app.dimensions.ai/details/publication/pub.1008022091"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-12-01T06:20", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_234.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf00941885"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    169 TRIPLES      21 PREDICATES      115 URIs      102 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00941885 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Nb947bcce272f425ba3f811e4f08a2bdd
    4 schema:citation sg:pub.10.1007/bf00928674
    5 sg:pub.10.1007/bf00928709
    6 sg:pub.10.1007/bf00934589
    7 sg:pub.10.1007/bf00937371
    8 sg:pub.10.1007/bf00940054
    9 schema:datePublished 1993-10
    10 schema:datePublishedReg 1993-10-01
    11 schema:description Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm−1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.
    12 schema:genre article
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N0778297e4da94a25b6cb33b95ddb0f5f
    15 N44e71edbe66043fcabbb801ea0aa5d19
    16 sg:journal.1044187
    17 schema:keywords MPS
    18 achievable
    19 algebraic system
    20 algorithm
    21 approach
    22 boundary value problem
    23 cases
    24 computation
    25 computational effort
    26 computer
    27 conditions
    28 considerable interest
    29 constants
    30 continuity conditions
    31 decomposition technique
    32 different initial conditions
    33 different processors
    34 differential systems
    35 dimensions
    36 discrete version
    37 domain
    38 drawbacks
    39 efficient solution
    40 efforts
    41 features
    42 first subinterval
    43 guidance
    44 implementation
    45 initial conditions
    46 intercommunication
    47 interest
    48 interface
    49 interface conditions
    50 iterative solution
    51 key
    52 large linear algebraic systems
    53 linear algebraic system
    54 linear problem
    55 linear transformation
    56 means
    57 method
    58 multi-point approach
    59 nature
    60 nonhomogeneous systems
    61 nonlinear problems
    62 numerical tests
    63 optimization
    64 parallel algorithm
    65 parallel computation
    66 parallel computers
    67 parallelism
    68 particular nature
    69 particular solutions
    70 present technique
    71 problem
    72 processors
    73 quasilinearization technique
    74 real-time trajectory optimization
    75 requirements
    76 same size
    77 separate tasks
    78 sequence
    79 sequential algorithm
    80 size
    81 solution
    82 speedup
    83 state domain
    84 state vector
    85 subintervals
    86 subsequent subintervals
    87 substantial speedup
    88 system
    89 task
    90 technique
    91 test
    92 time domain
    93 time subinterval
    94 trajectory optimization
    95 transformation
    96 two-point boundary value problem
    97 two-point case
    98 vector
    99 vector of constants
    100 version
    101 wheren
    102 schema:name Parallel computation of two-point boundary-value problems via particular solutions
    103 schema:pagination 5-29
    104 schema:productId N1ab16bf6c6984ffab461653b0c431e2c
    105 Ned69eef8c3df4a04b56d418bd068d9de
    106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008022091
    107 https://doi.org/10.1007/bf00941885
    108 schema:sdDatePublished 2022-12-01T06:20
    109 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    110 schema:sdPublisher N59a177ddd61942e3b83434f11e750098
    111 schema:url https://doi.org/10.1007/bf00941885
    112 sgo:license sg:explorer/license/
    113 sgo:sdDataset articles
    114 rdf:type schema:ScholarlyArticle
    115 N0778297e4da94a25b6cb33b95ddb0f5f schema:volumeNumber 79
    116 rdf:type schema:PublicationVolume
    117 N1ab16bf6c6984ffab461653b0c431e2c schema:name dimensions_id
    118 schema:value pub.1008022091
    119 rdf:type schema:PropertyValue
    120 N44e71edbe66043fcabbb801ea0aa5d19 schema:issueNumber 1
    121 rdf:type schema:PublicationIssue
    122 N59a177ddd61942e3b83434f11e750098 schema:name Springer Nature - SN SciGraph project
    123 rdf:type schema:Organization
    124 Na33e2717e91046e9b19aaf646b8615bb rdf:first sg:person.014414570607.44
    125 rdf:rest rdf:nil
    126 Nb947bcce272f425ba3f811e4f08a2bdd rdf:first sg:person.015552732657.49
    127 rdf:rest Na33e2717e91046e9b19aaf646b8615bb
    128 Ned69eef8c3df4a04b56d418bd068d9de schema:name doi
    129 schema:value 10.1007/bf00941885
    130 rdf:type schema:PropertyValue
    131 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    132 schema:name Mathematical Sciences
    133 rdf:type schema:DefinedTerm
    134 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    135 schema:name Numerical and Computational Mathematics
    136 rdf:type schema:DefinedTerm
    137 sg:journal.1044187 schema:issn 0022-3239
    138 1573-2878
    139 schema:name Journal of Optimization Theory and Applications
    140 schema:publisher Springer Nature
    141 rdf:type schema:Periodical
    142 sg:person.014414570607.44 schema:affiliation grid-institutes:grid.21940.3e
    143 schema:familyName Wang
    144 schema:givenName T.
    145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014414570607.44
    146 rdf:type schema:Person
    147 sg:person.015552732657.49 schema:affiliation grid-institutes:grid.21940.3e
    148 schema:familyName Miele
    149 schema:givenName A.
    150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015552732657.49
    151 rdf:type schema:Person
    152 sg:pub.10.1007/bf00928674 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018094581
    153 https://doi.org/10.1007/bf00928674
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/bf00928709 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052124489
    156 https://doi.org/10.1007/bf00928709
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/bf00934589 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036234620
    159 https://doi.org/10.1007/bf00934589
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/bf00937371 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008341596
    162 https://doi.org/10.1007/bf00937371
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/bf00940054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007660607
    165 https://doi.org/10.1007/bf00940054
    166 rdf:type schema:CreativeWork
    167 grid-institutes:grid.21940.3e schema:alternateName Aero-Astronautics Group, Rice University, Houston, Texas
    168 schema:name Aero-Astronautics Group, Rice University, Houston, Texas
    169 rdf:type schema:Organization
     




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


    ...