Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations

References

• Abbott J, Mulders T (2001) How tight is Hadamard’s bound? Experiment. Math. 10(3):331–336.Crossref, Google Scholar
• Applegate DL, Dash S, Cook W (2005) QSopt linear programming solver. Accessed January 5, 2015, http://www.math.uwaterloo.ca/~bico//qsopt/.Google Scholar
• Applegate DL, Cook W, Dash S, Espinoza DG (2007a) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Applegate DL, Dash S, Cook W, Espinoza DG (2007b) QSopt_ex. Accessed January 6, 2015, http://www.dii.uchile.cl/~daespino/.Google Scholar
• Bareiss EH (1968) Sylvester’s identity and multistep integer-preserving Gaussian elimination. Math. Comput. 22(103):565–578.Google Scholar
• Bareiss EH (1972) Computational solutions of matrix problems over an integral domain. IMA J. Appl. Math. 10(1):68–104.Crossref, Google Scholar
• Cook W, Steffy DE (2011) Solving very sparse rational systems of equations. ACM Trans. Math. Software (TOMS) 37(4):39:1–39:21.Crossref, Google Scholar
• Dhiflaoui M, Funke S, Kwappik C, Mehlhorn K, Seel M, Schömer E, Schulte R, Weber D (2003) Certifying and repairing solutions to large LPS how good are LP-solvers? Proc. Fourteenth Ann. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 255–256.Google Scholar
• Dixon JD (1982) Exact solution of linear equations using P-ADIC expansions. Numerische Mathematik 40(1):137–141.Crossref, Google Scholar
• Eberly W, Giesbrecht M, Giorgi P, Storjohann A, Villard G (2006) Solving sparse rational linear systems. Proc. 2006 Internat. Sympos. Symbolic and Algebraic Computation (ACM, New York),63–70.Crossref, Google Scholar
• Edmonds J (1967) Systems of distinct representatives and linear algebra. J. Res. National Bureau Standards Sect. B 71:241–245.Crossref, Google Scholar
• Edmonds J, Maurras JF (1997) Note sur les q-matrices d’Edmonds. RAIRO Oper. Res. 31(2):203–209.Crossref, Google Scholar
• Fang XG, Havas G (1997) On the worst-case complexity of integer Gaussian elimination. Proc. 1997 Internat. Sympos. Symbolic and Algebraic Comput. (ACM, New York), 28–31.Crossref, Google Scholar
• Gentleman WM, Johnson SC (1976) Analysis of algorithms, a case study: Determinants of matrices with polynomial entries. ACM Trans. Math. Software (TOMS) 2(3):232–241.Crossref, Google Scholar
• Gleixner AM, Steffy DE, Wolter K (2012) Improving the accuracy of linear programming solvers with iterative refinement. Proc. 37th Internat. Sympos. Symbolic Algebraic Comput. (ACM, New York), 187–194.Crossref, Google Scholar
• Golub GH, Van Loan CF (2012) Matrix Computations, Vol. 3 (Johns Hopkins University Press, Baltimore).Google Scholar
• Hadamard J (1893) Résolution d’une question relative aux déterminants. Bull. Sci. Math. 17(1):240–246.Google Scholar
• Kaltofen E, Lobo A (1999) Distributed matrix-free solution of large sparse linear systems over finite fields. Algorithmica 24(3–4):331–348.Crossref, Google Scholar
• Kaltofen E, Saunders BD (1991) On Wiedemann’s method of solving sparse linear systems. Sakata S, Goos G, Hartmanis J, eds. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Springer-Verlag, Tokyo), 29–38.Crossref, Google Scholar
• Knuth DE (1981) The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 2nd ed. (Addison-Wesley Professional, Boston).Google Scholar
• Koch T (2004) The final NETLIB-LP results. Oper. Res. Lett. 32(2):138–142.Crossref, Google Scholar
• Lee HR, Saunders BD (1995) Fraction-free Gaussian elimination for sparse matrices. J. Symbolic Comput. 19(5):393–402.Crossref, Google Scholar
• Montante-Pardo RM, Méndez-Cavazos MA (1977) Un método númerico para cálculo matricial. Revista Técnico-Científica de Divulgación 2:1–24.Google Scholar
• Mulders T, Storjohann A (2000) Rational solutions of singular linear systems. Proc. 2000 Internat. Sympos. Symbolic Algebraic Comput. (ACM, New York), 242–249.Crossref, Google Scholar
• Nakos GC, Turner PR, Williams RM (1997) Fraction-free algorithms for linear and polynomial equations. ACM SIGSAM Bull. 31(3):11–19.Crossref, Google Scholar
• Neumaier A, Shcherbina O (2004) Safe bounds in linear and mixed-integer linear programming. Math. Programming 99(2):283–296.Crossref, Google Scholar
• Schönhage DDA, Strassen V (1971) Schnelle Multiplikation grosser Zahlen. Computing 7(3–4):281–292.Crossref, Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (Wiley, Chichester, UK).Google Scholar
• Wan Z (2006) An algorithm to solve integer linear systems exactly using numerical methods. J. Symbolic Comput. 41(6):621–632.Crossref, Google Scholar
• Wiedemann D (1986) Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory 32(1):54–62.Crossref, Google Scholar
• Zhou W, Jeffrey DJ (2008) Fraction-free matrix factors: New forms for LU and QR factors. Frontiers Comput. Sci. China 2(1):67–80.Crossref, Google Scholar