Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

To resolve issues starting MATLAB on Mac OS X 10.10 (Yosemite) visit: http://www.mathworks.com/matlabcentral/answers/159016

How would i modify this script If i wanted to do integer only Gaussian elimination on a system of linear equations (Ax=b)?

Asked by Scott Jones on 20 Nov 2012
      function [x] = IntegerGaussrevised(A,b)
  n = size(A,1);  %getting n
  A = [A,b];      %produces the augmented matrix

%elimination process starts

for i = 1:n-1
    p = i;
%comparison to select the pivot
      for j = i+1:n
          if abs(A(j,i)) > abs(A(i,i))
              U = A(i,:);
              A(i,:) = A(j,:);
              A(j,:) = U;        
          end
      end
%cheking for nullity of the pivots
      while A(p,i)== 0 && p <= n
          p = p+1;
      end
      if p == n+1
          disp('No unique solution');
          break
      else
          if p ~= i
              T = A(i,:);
              A(i,:) = A(p,:);
              A(p,:) = T;
          end
      end
      for j = i+1:n
          m = A(j,i)/A(i,i);
          for k = i+1:n+1 
              A(j,k) = A(j,k) - m*A(i,k);
          end
      end
  end

%checking for nonzero of last entry

if A(n,n) == 0
    disp('No unique solution');
    return
end

%backward substitution

x(n) = A(n,n+1)/A(n,n);
for i = n - 1:-1:1
    sumax = 0;
    for j = i+1:n
        sumax = sumax + A(i,j)*x(j);
    end
    x(i) = (A(i,n+1) - sumax)/A(i,i);
end
end
  end
Scott Jones

Products

1 Answer

Answer by Jan Simon on 21 Nov 2012
Edited by Jan Simon on 21 Nov 2012

Please follow Matt J's advice to format the code properly.

Does "integer only" mean, that all occurring values are integers? Then the modifications concern one line only:

m = A(j,i) / A(i,i);

Here fractional parts can be introduced. So check at first, if the result is an integer: m ~= floor(m). If this is not the case, multiply theother lines of the augm,ented Matrix by A(i,i).

But this will fail when there is an overflow: Numbers greater than 2^52 cannot be represented exactly with double precision. Therefore my suggestion has severe limits. Even for tiny matrices (< 10 rows) this can fail, if the elements are in the magnitude of 1000.

So perhaps you are looking for something completely different.

1 Comment

Scott Jones on 8 Dec 2012

Hey, sorry it took me so long to sort the code out. My question is poorly worded as well. What I meant by integer only Gaussian elimination Integer was a way for to do it that involves ensuring that at each stage in the elimination process the augmented matrix for the system must contain only integers. (inputs are also integers). Thanks for all of your help so far really appreciate you taking the time to try and help.

Jan Simon

Contact us