How to solve for all IRR roots in SAS IML

[tsimpson]

I am working on a research project that calculates the internal rate of return given various cash inflows and outflows. IRR can be calculated as:

CFo(1+IRR)^n + CF1(1+IRR)^(n-1) + CF2 (1+IRR)^(n-2) + ...+ CFn = 0.

Thus, in other words, IRR is a root of high-order polynominal. In my sample, n varies  for each project and it could be as high as 168. Following are two issues that I have been struggling for a long time and hope that someone could help me to the right direction:

(1) As IRRs are roots of a polynomial function, it is possible to encounter muptiple IRR. For my sample, due to many sign changes, this problem is prevalent and I am wondering if there is a way to get SAS to calculate ALL these roots, instead of giving just one IRR, along with the warnings of potential multiple IRRS.

(2) In Excel, one has an option of setting the seed (guess rate) as a starting point and I am hoping that SAS IML has similar function such that I could set the starting rate for IRR. Are you aware of any way that I could set the starting guess rate for IRR in SAS?

Any help/ suggestion that you could point me to solve these problems is greatly appreciated.

[Rick_SAS]

From a numerical analysis perspective, there are several problems with this approach (for details, see a numerical analysis book such as Conte and deBoor):

1) High-degree polynomials are numerically unstable. It is difficult to even evaluate a high-degree polynomial because (a) the polynomial overflows when x (=1-IRR) is modestly large (for example |x|>50)

2) Algorithms for finding the roots of polynomials (for example, the POLYROOT function in SAS/IML) tend to become less accurate as the degree grows. (This is not a problem with SAS; I am not aware of ANY algorithm that can reliably find roots of a 168-degree polynomial!)

3) Most of the roots of your polynomial are complex, but I assume you are only interested in real roots. Finding real roots of a high-degree polynomial is known to be difficult.

That said, here's some analysis about the way to attempt this in SAS:

A) No, you can't set a starting condition for the IRR function.

B) You can try to use POLYROOT in SAS/IML, but that tries to find ALL roots (including complex), so you'll run into problems as described above.

C) The most practical approach is to use Newton's method (http://blogs.sas.com/content/iml/2011/08/05/using-newtons-method-to-find-the-zero-of-a-function/) or Bisection (http://blogs.sas.com/content/iml/2011/08/03/finding-the-root-of-a-univariate-function/) to try to find real roots, especially if you can bound the roots (for example, you only want IRR in [0,1]).  You can use Horner's Method (sometimes called Horner's Scheme) to evaluate the polynomial efficiently.

One parting remark: Suppose you have a high-degree monomial such as x##n (n=168 in your example).  For what values of x will x##n be less than 10##(-308), which is the smallest representable double-precision value? A little algebra shows that is x < 10##(-1.8) = 0.16, then x##168 will evaluate to ZERO.  Thus you are going to have problems finding roots close to zero.