Texas A&M University LibrariesTexas A&M University LibrariesTexas A&M University Libraries
    • Help
    • Login
    OAKTrust
    View Item 
    •   OAKTrust Home
    • Colleges and Schools
    • Office of Graduate and Professional Studies
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    • View Item
    •   OAKTrust Home
    • Colleges and Schools
    • Office of Graduate and Professional Studies
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    The full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period, even for Texas A&M users with NetID.

    Foundational Factorization Algorithms for the Efficient Roundoff-Error-Free Solution of Optimization Problems

    Thumbnail
    View/Open
    ESCOBEDO-DISSERTATION-2016.pdf (1.387Mb)
    Date
    2016-08-01
    Author
    Escobedo, Adolfo Raphael
    Metadata
    Show full item record
    Abstract
    LU and Cholesky factorizations play a central role in solving linear and mixed-integer programs. In many documented cases, the round-off errors accrued during the construction and implementation of these factorizations cause the misclassification of suboptimal solutions as optimal and infeasible problems as feasible and vice versa. Such erroneous outputs bring the reliability of optimization solvers into question and, therefore, it is imperative to eliminate these round off errors altogether and to do so efficiently to ensure practicality. Firstly, this work introduces two round off-error-free factorizations (REF) constructed exclusively in integer arithmetic: the REF LU and Cholesky factorizations. Additionally, it develops supplementary integer-preserving substitution algorithms, thereby providing a complete tool set for solving systems of linear equations (SLEs) exactly and efficiently. An inherent property of the REF factorization algorithms is that their entries' bit-length--- i.e., the number of bits required for expression--- is bounded polynomially. Unlike the exact rational arithmetic methods used in practice, however, the algorithms herein presented do not require any greatest common divisor operations to guarantee this pivotal property. Secondly, this work derives various useful theoretical results and details computational tests to demonstrate that the REF factorization framework is considerably superior to the rational arithmetic LU factorization approach in computational performance and storage requirements. This is significant because the latter approach is the solution validation tool of choice of state-of-the-art exact linear programming solvers due to its ability to handle both numerically difficult and intricate problems. An additional theoretical contribution and further computational tests also demonstrate the predominance of the featured framework over Q-matrices, which comprise an alternative integer-preserving approach relying on the basis adjunct matrix. Thirdly, this work develops special algorithms for updating the REF factorizations. This is necessary because applying the traditional approach to the REF factorizations is inefficient in terms of entry growth and computational effort. In fact, these inefficiencies virtually wipe out all the computational savings commonly expected of factorization updates. Hence, the current work develops REF update algorithms that differ significantly from their traditional counterparts. The featured REF updates are column/row addition, deletion, and replacement.
    URI
    http://hdl.handle.net/1969.1/157772
    Subject
    Exact mathematical programming
    exact algorithms
    matrix factorizations
    roundoff errors
    solving linear systems
    factorization update algorithms.
    Collections
    • Electronic Theses, Dissertations, and Records of Study (2002– )
    Citation
    Escobedo, Adolfo Raphael (2016). Foundational Factorization Algorithms for the Efficient Roundoff-Error-Free Solution of Optimization Problems. Doctoral dissertation, Texas A & M University. Available electronically from http : / /hdl .handle .net /1969 .1 /157772.

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Advanced Search

    Browse

    All of OAKTrustCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDepartmentThis CollectionBy Issue DateAuthorsTitlesSubjectsDepartment

    My Account

    LoginRegister

    Statistics

    View Usage Statistics
    Help and Documentation

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV