I am attaching a C Program for Lu method.

Here is the c program by me.

The algorithm is for a system of n eqns. in unknowns., the usual Gauss elimination. We usually employ partial pivoting and at each stage exchange rows to get the biggest element in magnitude as pivot. divides the eqn( row) by pivot then use scalar multiples of this row subtract it from the all eons( rows after this) to get all elements zero in the column. finally we get each unknown by backward substitution.

A drawback of the above system is that if Rhs vector changes but not the coefficient matrix one has to do Gauss elimination all over again. to avoid This we slightly modify Gauss elimination and store the bok keeping information in the matrix itself. so in the end the matrix is sorted in place into two factors L and U with digonals of U implicitly one.

now Gauss elimination can be performed over integers where we nned not make pivot one but just use cross multiplication . the problem is to find an analogue of LU in integers so that this can be done. ( in present Lu algorithm pivot has to be made one which involves use of division).

we would like division relegated in last step of forward and backward substitution. But the present formulation of LU which facilitates book keeping is such that it rests on the operation of pivot one. one has to modify the LU algorithm.

an explanation of LU using Gauss elimination can be found in the book of Sastry. (PHI ) . there was an AMS article last year ( notices of American Mathematical society citing 200 years of Gauss elimination.

once this is modified one can look for ways to avoid making pivot one in simplex method . the idea is that then these methods will work on integers and produce rational solutions. a comp handles float and int in intrinsically different ways.

The code is just attched to help users to understand and expeiemtn this method.

then point is that while gauss elimnation can be modified as lu factorization algorithm for real numbers , over intehgers gauss elimnation as done in high school seems to be the only alternative and there is no efficient way for bookkeeping row transformations soi as to generate lu factorization. .

It may interest you to know that the first electronic digital computer solved Ax=b up to 29 equations in 29 unknowns, and did it with 50-bit integers! This is the Atanasoff-Berry Computer (ABC), which has been reconstructed and you can still see it in the Computer History Museum.

The key to the algorithm is to allow right shifts of the binary integers, which is obviously trivial compared with division. In using a pivot x1 to eliminate a value x2 in another row, you shift (a copy of) the entire matrix row containing x1 right until it is smaller magnitude than x2. Then you add or subtract the row with x1 and the row with x2, and it will eliminate a leftmost bit in x2. Repeat this until all bits in x2 have been eliminated, and you will have effectively multiplied the first row by (x2/x1) and subtracted it from the second row, but doing it one bit at a time makes the division implicit. If any pivot selection was done, it was done by the human operator, who kept piles of paper cards with the intermediate answers punched in them.

Some of you may be appalled by the potential for roundoff error, which is certainly larger than with IEEE floating-point numbers. The ABC just truncated the right-shifts without rounding. But if you think about it, that would tend to be randomly up or down, so the actual bit accuracy loss was generally on the order of sqrt(50) per row elimination. And that's one reason Atanasoff used 50 bits, almost as many as in the fraction bits of a modern double-precision float.

Given an Ax=b problem to solve, Atanasoff would scale the problem up to come close to the maximum 50 bit representation, since scaling A and b doesn't change x, and it gives more protection against rounding.

Respected sir,

u have not lloked into the program added as attachement. it is well known that lu factorization could be efected using gauus elimnation. and this solves asystem of equations. once the coefficent atrix is factorized then any system withsame coefficent matrix but differenr rhs can be solved.

gauus elimantio could be done in integers but to do lu must divide by pivot. this involves going into lrational/real numbers even if final ansewer is integer. my question is purely algebraic one can lyu alogorithm be so modified so taht division need not be done until last stage so that remaining in integers one can do lu factorization ,

Working on integers without performing divisions (i.e. solving exactly without rounding) is possible and is called fraction-free LU.

A nice reference is: W. Zhou, D.J. Jeffrey, Fraction-free matrix factors: new forms for LU and QR factors, Front. Comput. Sci. China 2 (1) (2008)1–13. doi: 10.1007/s11704-008-0005-z

Main drawbacks is the very rapid increase in the integer ranges (the number of digits may increase dramatically, and sometimes a library for arbitrary adaptive precision algebra is needed).

Actually it operates on an integral domain, and the solution is in the associated quotient space. There are applications in symbolic computations on polynomials and implementations (may be partial ones) in fflas library

J.-G. Dumas, P. Giorgi, C. Pernet, Dense linear algebra over word-size prime fields: the FFLAS and FFPACK packages, ACM Trans.Math. Software 35 (3) (2008) 19:1–19:42. doi: 10.1145/1391989.1391992, URL:

and in SymPy package

SymPy Development Team, SymPy: Python library for symbolic mathematics, 2011. Available from: .

Concerning a generalized inverse, you may eventually refer to

D. Dureisseix, Generalized fraction-free LU factorization for singular systems with kernel extraction, Linear Algebra and its Applications 436, 1 (2012) 27-40, DOI : 10.1016/j.laa.2011.06.013

Please see my recent paper on application of fraction-free LU method (G. Korres)

There is another approach called Integer Preserving Gaussian Elimination that starts with integer values and performs an LU decomposition in a manner that not only preserves integrality, but establishes a bound on the growth of the integer factors as well, apparently unlike the paper from China referenced above. I think the original methods were discovered by someone named Bareiss and also the legendary Jack Edmonds, but I don't think they ever actually worked on industrial strength implementation. However, a fair amount of work has been done with this in the last decade by Erick Centeno Moreno of Texas A&M, so you could start with his faculty web page (https://engineering.tamu.edu/industrial/profiles/emorenocenteno.html) if you wanted to dig deeper.