1. Field
The present disclosure relates to the field of ill conditioning, and specifically, determining whether square linear systems of equations are ill conditioned.
2. Description of Related Art
Analytics systems are often used in business applications. Business Analytics use statistical and quantitative methods on data to perform forward looking analysis. Applying quantitative optimization methods to business analytics problems can enable companies to more effectively handle the complexity and large amounts of data in their operations.
IBM® ILOG® CPLEX®, also known as CPLEX, named for the simplex method in combination with the C programming language, is software from the IBM Corporation. CPLEX can solve mathematical optimization problems arising from business analytics models as well as other scientific computing applications. All of CPLEX's algorithms come from the field of mathematical programming, and they involve computing solutions to square linear systems of equations. CPLEX can solve optimization models in numerous industries, including production planning in manufacturing processes, crew scheduling in the airlines industry, vehicle routing and delivery in the transportation industry, and computational biology in medicine. However, within analytics systems, such as CPLEX, ill conditioning in the square linear systems of equations can occur.
Ill conditioning, which is a concept of scientific computing and numerical linear algebra, is a situation in which a small change in an input value to a mathematical model can result in a large change to the computed solution or output value. For example, square linear systems of equations can be determined to be ill conditioned if a condition number is large, and it can be determined to be well conditioned if the condition number is small. Further, as the value of a condition number increases, the change in the computed solution or output value has the potential to increase relative to the change in input data.
Computers have a limited number of bits to represent numeric values. The typical floating point system used by computers cannot represent all rational numbers exactly, and any system with a finite number of bits cannot represent all real numbers exactly. Therefore, scientific computing applications often cannot exactly represent the mathematical systems they model. In other words, these floating point systems have finite precision.
A computer's machine precision represents the rounding error that can arise from the finite precision in the representation of such numerical values. The condition number of a square matrix corresponding to a linear system of equations provides a multiplicative factor of the change in input value that can manifest itself in the computed solution or output value. Specifically, consider a matrix A with m rows and m columns, and m vectors x and b of variables and data, respectively. For a given change in the input in either A or b, the condition number of A provides a measure of the change in output in the computed solution x of the square linear system Ax=b. The condition number of the matrix A associated with this linear system can be quantitatively derived asK(A)=∥A∥*∥A−1∥
If a computing application that solves such square linear systems is run on a computer with finite precision, then the machine precision provides a measure of the minimum change in the input. Letting Δ represent the small change in input to the data of the linear system in A or b, then K(A)*Δ provides an upper bound on the change to the computed solution x. From this product of K(A) and Δ we see that larger condition numbers imply larger potential changes in the computed solution. Such large condition numbers can make seemingly irrelevant changes to the input yield much larger changes in the output.
Even if a mathematical model formulator does not change the data, finite precision computers can introduce small changes into square linear systems of equations, which could result in a large change to the computed solutions or output values. For example, if a user moves their program from a machine having a Microsoft Windows® operating system to a machine having an IBM AIX® operating system, the move can change the machine precision enough to significantly influence results if square linear systems of equations are ill conditioned.
However, there currently does not exist any method for quantitatively assessing ill conditioning in a square linear system of equations. The current state of the art does not determine what constitutes a large or a small condition number when assessing the conditioning of a square linear system of equations. Also, there is no known method for addressing ill conditioning in algorithms, such as linear, mixed integer, quadratic, and nonlinear programming algorithms, that solve a series of interrelated square linear systems of equations.
In the current art, many programs do not address the issue of ill conditioning of square linear systems of equations. At most, in the event square linear systems of equations are determined to be ill conditioned, the current art would merely display a single condition number. The user would then have to determine whether the value of the condition number is sufficiently large to make the system ill conditioned. Further, when addressing only a single condition number from a single linear system of equations, the situation in which a sequence of condition numbers are generated, is not addressed. In some instances, examining a single condition number would give a partial view of ill conditioning for a particular problem.