A Block-$LU$ Update for Large-Scale Linear Programming (Q3988985)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 33651
Language Label Description Also known as
default for all languages
No label defined
    English
    A Block-$LU$ Update for Large-Scale Linear Programming
    scientific article; zbMATH DE number 33651

      Statements

      A Block-$LU$ Update for Large-Scale Linear Programming (English)
      0 references
      0 references
      0 references
      28 June 1992
      0 references
      matrix factorization
      0 references
      simplex method
      0 references
      large sparse linear programming problem
      0 references
      block-LU update
      0 references
      updating
      0 references
      numerical experiments
      0 references
      test problems
      0 references
      stability
      0 references
      The paper deals with the simplex method for the standard large sparse linear programming problem. Stable and efficient updates to the basis matrix factors are vital to the computational success. The updating technique of \textit{P. E. Gill}, \textit{W. Murray}, the second author and \textit{M. H. Wright} [SIAM J. Sci. Stat. Comput. 5, 562--589 (1984; Zbl 0559.65042)], based on the block-LU factors of an expanding basis is examined. The main conclusions are: a) the block-LU update technique is a viable alternative to the standard updating technique of Bartels and Golub [cf. \textit{R. H. Bartels}, Numer. Math. 16, 414--434 (1971; Zbl 0197.43305)] when vectorization is available, b) numerical experiments on a CRAY Y-MP show the block-LU update to be superior to Bartels-Golub updating on 27 of 30 large, sparse test problems, c) the block-LU update possesses the same stability properties as the update of Bartels and Golub.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references