Jump to content

Hypergeometric formula

Guest fornorton

Recommended Posts

Guest fornorton

Hi there!


I am trying to calculate the complexity of an algorithm and I have concluded that it takes a number of steps given by the following formula (in Mathematica notation):


Hypergeometric1F1(-D, 2, -x)


This looks like a multinomial of x. The order of this polynomial is D. The last term of this polynomial is x^D/D!, which converges to 0 when D is large enough. On the contrary, the first terms seem to be significant.


Do you have any suggestions for the complexity of the algorithm? Is it polynomial or exponential with respect to D?


Thanks in advance!

Link to comment
Share on other sites

What is D ?

If D > 0 and if D is an integer indeed the series will terminate and your hypergeometric function will be a polynomial.

What do you mean with x^D/D! converges to zero ? (You should at least keep x fixed in such an argument).


Anyway the way you write down the hypergeometric function the D! will be in the upperpart of the fraction, so you have more something like D! x^D then x^D/D!


A quick maple calculation shows that hypergeom(-D;2:-x) behaves like :

1 + 1/2 D x + 1/12 D (D - 1) x^2 + 1/144 D (D - 1) (D - 2) x^3 + 1/2880 D (D - 1) (D - 2) (D - 3) x^4 + 1/86400 D (D - 1) (D - 2) (D - 3) (D - 4) x^5 + 1/3628800 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) x^6 + 1/203212800 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) x^7 + 1/14631321600 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) (D - 7)x^8 + 1/1316818944000 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) (D - 7) (D - 8) x ^9 + O(x^10)


Your algorithm looks more factorial than anything else i think.



Link to comment
Share on other sites

Guest fornorton

My mistake... I should have given you more information. In my case, D is the number of dimensions of my problem. So, consider D as a positive integer variable. As D increases, my problem becomes harder to solve. What I am searching for is how much harder it becomes.


In your maple representation the factor of the last term is


(D!) / (D!)^2 =

= 1/(D!)


This is the reason why I said that the last term is:


(x^D) / (D!)


D! increases faster than x^D, as D becomes larger. So, in my opinion,


(x^D) / (D!) -> 0


But then, which term of the multinomial is the greatest? What is the order of this multinomial? And finally, what is the complexity of the algorithm?


I hope that everything is more clear now. I am expecting for further suggestions.

Link to comment
Share on other sites

You still didnt say what is x. But your algorithm is exponential in the size of your problem instance D. (since you have a lot of terms of the type x^(something with D), like D, D - 1 etc...

The bigger D, the more terms you have. The only reason in the last term X^D, you have something like x^D/D! is because you have D! x^n/n!^2 for n =D, so maybe you can estimate the terms before ?

Something like the coefficient of the n-1ste term behave at least like .... (something with n) and at most like (something with n), that way you know how your function behave approximately and you can send n to infinity and maybe use some of the assymptotic formula for hypergeometric fucntions. (Remember that they are each a solution to some differential equation).



Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.