Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Alam

Fast Numerical Gradient required

This topic is 5875 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! I have a multi-objective function. It''s analytical gradient is difficult to calculate. I am using the central forward method to find its grdient like given below: F = f(x1,x2,............,xn) del = 0.00000001 then grdient g_i with respect to x_i is g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del) g_2 = [f(x1, x2+del,....,xn) - f(x1, x2-del,...,xn)]/(2*del) . . . g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn-del)]/(2*del) Problem arises when n increase and it takes a long time. Any suggestion to make it fast ?????? Regards Alam

Share this post


Link to post
Share on other sites
Advertisement
You are trying to calculate n values. The time this takes has to be O(n). Even if you had the analytical solution.

The only optimisation that occurs to me would be possible if some of the parameters were independant of each other.

---------------------------
I may be getting older, but I refuse to grow up

Share this post


Link to post
Share on other sites
quote:
Original post by Alam
F = f(x1,x2,............,xn)
del = 0.00000001
then grdient g_i with respect to x_i is
g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del)
g_2 = [f(x1, x2+del,....,xn) - f(x1, x2-del,...,xn)]/(2*del)
.
.
.
g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn-del)]/(2*del)



I haven''t tried anything like this before, so this might not be an acceptable optimization. What I''d suggest is changing the equations to:

g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]/(del)
g_2 = [f(x1, x2+del,....,xn) - f(x1, x2,...,xn)]/(del)
.
.
.
g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn)]/(del)

but that might lose some accuracy or something. Maybe you''d want to double the size of del if floating point errors become significant. What it obviously achieves is only calculating the right hand f()s once, rather than n times. This wouldn''t really help much if the time to compute f() is small.

What is f? Perhaps someone could solve this analytically for you?

Miles

Share this post


Link to post
Share on other sites
quote:
Original post by Alam
Hello!
I have a multi-objective function. It''s analytical gradient is difficult to calculate. I am using the central forward method to find its grdient like given below:

F = f(x1,x2,............,xn)
del = 0.00000001
then grdient g_i with respect to x_i is
g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del)




This seems academic to me. What is your project?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites

Yes it is a accademic project. I am doing some kind of simulation/manipulation that needs energy minimization. For Steepest descent or conjugate gradient method gradient is needed.

Analytic method is fastest. Since F is complicated, it can create some error.

If i use farward method, [F(x+del)-F(x)]/del, accuracy is lost that i don''t want.
Actually F is a complex function, any change in x1, causes changes in many variable. Each x_i is linked with x_j (j=1,2...,m). So calculating function also take time.

Any idea to skip some terms and so on ?

Regards
Alam

Alam
-- Learning never ends --

Share this post


Link to post
Share on other sites
you can try to eliminate the division. but i don''t know if this changes anything.

try instead:

g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]/(del)

double invDel = 1.0 / del;

g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]*(invDel);

are there maybe some symmetries in the formula for g_1 to g_n like intermediate data that you have to calculate several times. if yes you could reuse them. how is f(...) defined? what size can n have at the top?

Share this post


Link to post
Share on other sites
quote:
Original post by Alam

Yes it is a accademic project. I am doing some kind of simulation/manipulation that needs energy minimization. For Steepest descent or conjugate gradient method gradient is needed.


Please understand that these forums are focused specifically on game development, and are not a general place for discussions not directly related to the game development industry.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
To Alam: It''s a pity you haven''t told any details of what you''re doing, as that would help a lot. The conjugate gradient method itself requires no gradient solving per iteration, you simply feed it the coefficient matrix A and the right side vector b and the CG algorithm solves Ax=b for the vector x, no numerical gradients required. Of course if the computation of A or b requires a gradient of some kind it''s different.

To GRhodes: I don''t think that kind of "this subject doesn''t belong to game development" will make games more diverse (simulation subjects are usually well suited for games, btw, for example physics simulation).

- Mikko Kauppila

Share this post


Link to post
Share on other sites
quote:
Original post by uutee
To GRhodes: I don''t think that kind of "this subject doesn''t belong to game development" will make games more diverse (simulation subjects are usually well suited for games, btw, for example physics simulation).


Of course you''re correct in what you say. My post was meant as a reminder, really, that I don''t want to deviate too far from game development. I''d really prefer to discuss, say, a physics simulation problem that is specifically being developed for a game project compared with a purely scientific university or commercial research project. Bandwidth and servers cost money. Gamedev.net is growing quite rapidly, and there is evidence that more bandwidth and server space will be necessary to keep going soon. We already had one crisis several months ago, and I fear another is coming. If we allow any and all "math & physics" topics, even those unrelated specifically to games, we''ll be at a crisis point much sooner. We''re nearly there already (it occasionally takes me several HOURS to successfully post a single reply to a thread due to server limit issues). My vision of the future? Eventually you''ll have to pay for gamedev. By occasionally controlling topics, that can be delayed. Note that these bandwidth/server comments are based on my opinion and observations/experiences/interpretation of comments from others and do not necessarily reflect the views of those who actually manage the hardware side of the site.

If I had thought this were a completely off topic post, I would have closed the thread. For example, I have a fairly strict policy on homework (many folks try to abuse these forums to get answers to their homework).

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!