What are good algorithms to solve equations (or systems of equations or differential equations) using cloud computing?

Question

Kenneth Tran · Answer

Absolutely. Researchers and programmers have done it (i.e. running parallel iterative solvers on remote clusters) for years, since the beginning of parallel computing.

However, note that the parallelization typically takes place in each iteration (rather than distributing the iterations).

------------------

If you specify a system of equations that you want to solve using an iterative method, it's likely that a parallel implementation of that method already exists freely on the internet.

Daren Scot Wilson · Answer

For the simplest physical systems, described by just one variable, let’s say [math]x[/math], where some law of physics says it must change at a rate depending on its current value, and perhaps on other things going that vary with time, the differential equation is

[math]\dot{x} = f(x,t)[/math]

One typically chooses some initial conditions, the value of [math]x[/math] to be a given number [math]x_0[/math] at some initial time [math]t=0[/math].

From the differential equation, we can compute a value for [math]\dot{x} = v = f(x_0, 0)[/math]. Pick a small time step, [math]\Delta t[/math], not too small and not too big. If [math]x[/math] is changing at a rate of [math]\dot{x}[/math], then soon, at [math]t = \Delta t[/math], it’ll have the value [math]x = x_0 + v \Delta t[/math]. Call this [math]x_1[/math].

We may now take [math]x_1[/math] and [math]t = t_1 = \Delta t [/math] as a new initial condition, and repeat. When [math]t[/math] has grown enough, perhaps to [math]t_20000[/math], we’re done. Plot all the [math]x_i[/math] values vs time, or otherwise make use of the results.

Step Size

The phrase “not too big, not too small” holds a lot of woe for the newbie at numerical integration.

Too big a [math]\Delta t[/math], and the value [math]f(x,t)[/math] gives for [math]\dot{x}[/math] is meaningless, because our simple linear extrapolation to find [math]x_{i+1}[/math] from [math]x_i[/math] is using only the slope at [math]x_i[/math]. This method, called Euler integration, leads to an inaccurate result. It’d be better to know the slope at [math]x_i[/math] and at [math]x_{i+1}[/math], and use their average, but that means knowing the answer to a question before being able to calculate that answer. There are ways of dealing with this problem, such as guessing [math]x_{i+1}[/math] using the very same linear extrapolation we are condemning as inaccurate. One good algorithm is the Runge-Kutta integration formula. I won’t go into it here, but I did describe it on one of the Stack Exchange sites [ https://stackoverflow.com/a/1689654/10468 ].

Too small a [math]\Delta t[/math], and truncation errors will ruin your results. I’ll leave it to you to read up on that, if you don’t already have experience with it.

Yeah Okay, but my physical system has more than one variable!

Any interesting system likely has many objects moving, many voltages and charges varying, many quantum particles doing whatever. So [math]x[/math] is now [math]\vec{x}[/math], a set of numbers, a vector. Three for the position of an object. Six if its position and orientation matter. Dozens to simulate a solar system (but see the next section) or millions for atoms in a simulated crystal. No matter how many, if the physical system can still be written as the change in all those variables as a function of those variables and time, the same sort of reasoning applies. You have N variable, a function taking those N and t, and at each time step compute N rates of changes, one for each variable. Each variable is linearly extrapolated to the next time point, or handled in more sophisticated ways such as Runge-Kutta.

Yeah Okay, but my physical system is second order!

This is a very common situation in simulation of physical systems, for vehicle simulators, for NASA’s space mission planning, for lots of things. There is not only a rate of change for some set of variables, but a second derivative. One of the basic laws of physics relevant to physics simulations is Newton’s 2nd Law:

[math]F=ma[/math]

F is given from the physics of springs, gravity, electromagnetism, and so forth. [math]a[/math] is defined as [math]\ddot{x}[/math]. Masses are usually given constants. Newton tells us the accelerations, and that influences the change of the system’s state. The differential equations used are almost always a matter of computing forces from a given system state - the positions and their time derivatives. The latter are typically velocities.

[math]v = \dot{x}[/math]

[math]a = f(\vec{x}, \vec{v},t)[/math]

Given the positions and velocities of all particles or objects we compute the second time derivatives. We get a bunch of numbers. What do we do with them? We can use our methods of integrating first-order differential equations, as described above, if we do a little trick. Define

[math]\vec{w} = (\vec{x}, \vec{v})[/math]

Instead of N values lumped into a vector, we have this hybrid vector of 2N elements. “But the units wouldn’t be consistent!” Yeah, well, just bribe the math cop to look the other way; it isn’t going to matter. It’s the state of a first-order time varying system. Its time derivative is:

[math]\frac{d}{dt}\vec{w} = (\dot{x}, \dot{v}) = (v, a)[/math]

and since [math]a = f(w,t)[/math], we write a bigger function [math]g[/math]

[math]g(\vec{w},t) = ( \vec{v}, f(\vec{x}, \vec{v}, t) )[/math]

so that

[math]\dot{w} = g(w,t)[/math]

where I left off the [math]\vec{\ }[/math] because when you sling these kinds of things around all day, those little arrows just get to be too redundant. Anyway, you have a first order differential equation you may integrate in an Euleresque way, or a la Runge-Kutta, or however you please.

Anonymous · Answer

I can describe how to solve ordinary differential equations (ODEs), but not partial differential equations (PDEs). Below is a list of methods you can use:

1. Separating Variables: If you have a differential equation in the form[math]\frac{dy}{dx} = f(x)*g(y)[/math] you can separate variables to get [math]y[/math] on one side and [math]x[/math] on the other side. Then, you just integrate both sides. [math]\int \frac{dy}{g(y)} = \int f(x) dx[/math].
2. Variable Substitution: A homogeneous function is defined as a function in which [math]f(tx, ty) = f(x, y)[/math], where t is a constant. In such a case, you can use u-substitution, where u is defined as [math]u = \frac{y}{x}[/math].
3. Integrating Factor: If you have an equation in the form [math]\frac{dy}{dx} + p(x)y = g(x)[/math], you can use the integration factor if [math]g(x) 
eq 0 [/math](if [math]g(x) = 0[/math] you can just use separation of variables). The integration factor is [math]e^{\int p(x) dx}[/math]. Both sides of the equation are to be multiplied by this integration factor, and then you integrate both sides.
4. Bernoulli Equation: The Bernoulli Equation is in the form [math]\frac{dy}{dx} + p(x)y = g(x)y^n[/math]. If you set [math]v = y^{(1-n)}[/math] , the equation becomes [math]\frac{dv}{dx} + (1-n)p(x)v = (1-n)g(x)[/math]. Note that this equation is in a form where we can use the integrating factor. n is a constant, so the right hand side is simply a function of x.
5. Exact Equation: Exact ODEs are in the form [math]M(x, y)dx + N(x, y)dy = 0[/math]. If the [math]\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}[/math], the ODE is exact. It that condition exists, it follows that there exists a function [math]H(x, y)[/math], such that the [math]\frac{\partial H}{\partial x} = M[/math], and the [math]\frac{\partial H}{\partial y} = N[/math]. You can then solve for H.

Awnon Bhowmik · Answer

Q. Solve [math]\dfrac{dx}{dt}=\omega A\cos (\omega t)[/math] given that [math]x(0)=0[/math]

Solution:

[math]\dfrac{dx}{dt}=\omega A\cos(\omega t)[/math]

[math]\implies dx=\omega A\cos(\omega t)\,dt[/math]

[math]\implies \displaystyle \int dx=\int \omega A\cos (\omega t)\,dt[/math]

[math]\implies x(t)=\dfrac{A\omega}{\omega}\sin(\omega t)+C[/math]

[math]\implies x(t)=A\sin(\omega t)+C[/math]

Using the initial condition, [math]x(0)=0[/math]

[math]\implies 0=A\sin 0+C[/math]

[math]\implies C=0[/math]

Hence

[math]x(t)=A\sin(\omega t)[/math]

Done!

Vinay Sharma · Answer

Calculus is the mathematics of change, and derivatives are used to represent rates of change. Thus, one of the most typical applications of calculus is to create a differential equation, which contains an unknown function y=f(x) and its derivative. Solving such equations usually yields knowledge on how quantities change, as well as perspective into why and how the changes occur. Differential equations can be solved in a variety of ways, including direct solution, graphing, and computer computations. The basic principles are introduced in this chapter and will be described in greater detail later in the course. In this part, we will look at what differential equations are, how to check their solutions, various techniques for solving them, including instances of common and useful equations.

General Differential Equations

Given the equation

that is a differential equation(https://www.doubtnut.com/learn/english/class-12/maths/chapter/differential_equations) since it has a derivative. Both variables x and y have a relationship: y is an undetermined function of x. Moreover, the derivative of y is on the left side of the equation. As a result, this equation can be interpreted as follows: Begin with a function y=f(x) and find its derivative. The solution must be three times two.

it is regarded a solution to a differential equation. A differential equation is a mathematical equation that involves an unknown function y=f(x) and one or more of its derivatives.

When f and its derivatives are substituted into the equation, a solution to a differential equation is a function y=f(x) that satisfies the differential equation. Visit this website to learn more about this subject. It is important to note that a solution to a differential equation is not always unique, owing to the fact that the derivative of a constant is always zero. y=x2+4 is, for example, a solution to the first differential equation. This concept will be revisited later in this section. For the time being, let's concentrate on what it implies for a function to become a solution toward a differential equation. It is useful to identify features of differential equations so that they may be discussed and classified more easily. The most fundamental property of a differential equation has been its order. The order of a differential equation is defined as the highest order of every derivative of the unknown function appearing in the equation.

General and Particular Solutions

As previously stated, the differential equation y'=2x has at least two solutions:

The last component, which is a constant, is the sole difference between these two answers. What happens if the final term is a different constant? Will this expression still be a differential equation solution? In fact, any function of the type

where C is any constant, is a solution.

is always 2x, regardless of the value of C. It is possible to demonstrate that any solution to this differential equation must be of the form

A general solution to a differential equation is demonstrated here. In this instance, we have complete freedom to select any solution; for example,

is a member of the family of solutions to this differential equation. This is referred to as a specific solution to the differential equation. If we are provided more knowledge about the problem, we can typically identify a specific solution.

Initial-Value Problems

Because a particular differential equation usually contains an unlimited number of solutions, it is natural to wonder which one we should pick. More information is required to select one option. An initial value, which is an ordered pair used to discover a specific solution, is one example of specific information that might be beneficial. An initial-value issue is a differential equation having one or more initial values. The number of initial values required for an initial-value issue is often equivalent to the order of the differential equation. For instance, when we have the differential equation y'=2x, then y(3)=7 is an initial value, and that these equations constitute an initial-value issue when combined. Because the differential equation y′′3y'+2y=4ex is of second order, we require two starting values.

When solving initial-value problems of order higher than one, utilize the same value for the independent variable. Initial values for this second-order equation may be y (0) =2 and y'(0) =1. An initial-value issue is formed by these two initial values and the differential equation. These are so-called because the independent variable in the unknown function is frequently t, which symbolizes time. As a result, a value of t=0 reflects the start of the problem. We frequently evaluate the forces operating on an item in physics and engineering applications, and utilize this knowledge to comprehend the ensuing motion that may occur. For example, if we start with an item on Earth's surface, gravity is the dominant force acting on that thing. This information, along with Newton's second rule of motion (in equation form F=ma, where F represents force, m represents mass, and a represents acceleration), can be used by physicists and engineers to construct a solvable equation.

You can learn more about differential equation along with many other important topics at doubtnut.com. You would be able to get all the right idea of the different concepts that would help in proving to be of much help to you. You should make sure to download the Doubtnut app that would make you get the right idea on the different learning resources. This would help you to feel quite glad of the right selection that you have made to make your learning effective. So, make sure to reap the ultimate benefits out of it.

Daniel McLaury · Answer

Of course if you just say "a system of nonlinear equations" then the functions involved in your equations could be arbitrarily bad -- noncomputable, say.  In some cases, solving the equation in any explicit form would literally be impossible.

To see how quickly this can get, observe that we can construct an entire function with prescribed values at the integers.  (Look up "interpolation" in a complex analysis text, for instance.)  So fix a numbering of Turing machines, and let [math]f[/math] be an entire function which is 0 at every non-halting Turing machine and 1 at every halting Turing machine.

Then solving [math]f(z)=0[/math] -- a system of one equation in one variable, where the only function involved is entire -- is at least as hard as the halting problem, which is uncomputable.

Okay, so what can we deal with?  Well, the first step up from linear equations would be systems of polynomial equations.  In general solving systems of polynomials is hard but doable; you can generally solve systems with arbitrarily many equations and up to, say, 15 to 20 variables on a desktop computer.

There are two general approaches that I know of.  One is to use Groebner basis techniques, which are essentially a generalization of Gaussian elimination to the polynomial context (where things get much more complicated).

The other I know less about, but the idea (as best as I understand it from hearing second-hand descriptions) is that if you have an isolated solution of a system of polynomials, there are already serious constraints on what it can be; each variable has to be an algebraic number of bounded degree.  So you use numerical methods to prove that a solution exists in some small disc, and then argue that there's only one number in that disc that could possibly be the solution.

Given that arbitrary systems of polynomials are already barely tractable, you can't really go much further and have general solutions, but of course there are tricks for specific sorts of systems.  If you want to know about those you could read through published documentation for various computer algebra systems.

Anonymous · Answer

It can be done using a Numerical method or symbolic computation (see, e.g., symbolic ode solver - Google Search).

There are equations bad enough to disallow either approach. A symbolic solver solves only a certain class of DE—a class for which the general analytical solution are known. A numerical method may not be suitable to a given DE. Unless a DE is well-known and has been solved (numerically or symbolically), solving it can take some research.

Anonymous · Answer

Yes, though most aren’t used much. As mentioned by the other poster, there are some neural networks that do this. My experience has involved more of the optimizers that solve PDEs (including genetic algorithms). Quite a few exist, and the packages that solve differential equations generally run on some sort of machine learning/optimization algorithm.

Mark Miller · Answer

For many years I didn't see the point of learning calculus in CS. I had two semesters of it (so, no diffEq). I went for 12 years without running into a need for it, and then I finally needed knowledge of diffEq for one project. I only figured this out 8 years later. At the time I floundered with the problem, not coming up with a solution. The project was for a small business that made mechanical equipment for hotels. We discussed a mechanical engineering concept I had never heard of before called "jerk." It's change in the rate of acceleration. In physics terms it's a 2nd-order differential equation, off of a formula for acceleration (a 1st-order diff. eq.). I didn't know that at the time. All I knew was the abstract idea of "change in the rate of acceleration."

I tried applying what I knew from freshman physics, just using algebra, but that didn't lead to the right answer. I ended up having to admit I couldn't do it. Now, I could probably figure it out, not because I've taken more calculus, but I recognize now what the problem actually was. I imagine that if I had taken diffEq I might've had a better chance of recognizing it at the time.

John Lang · Answer

Consider the following setup. Suppose you have data

[math]\vec{Y} = [Y(t_1), Y(t_2), \ldots, Y(t_N)][/math]

for times [math]t = t_1, t_2, \ldots, t_N[/math]

Suppose you have the differential equation

[math]\frac{dy}{dt} = f(y;\vec{p})[/math],

where [math]\vec{p} = (p_1,\ldots,p_n)[/math] are the unknown parameters. Denote the solution to the differential equation at times [math]t=t_1, \ldots, t_N[/math] with parameters [math]\vec{p}[/math] by

[math]\vec{y}_{\vec{p}} = [y(t_1;\vec{p}), y(t_2;\vec{p}), \ldots, y(t_N;\vec{p})][/math].

Your problem is to find the [math]\vec{p}[/math] that minimizes the objective function [math]\|\vec{Y}-\vec{y}_{\vec{p}}\|[/math], where [math]\|\cdot\|[/math] is your favorite norm.

Now it is just a matter of applying your favorite optimization algorithm. For example, you could apply the Secant method in 1-D (n=1) or Broyden's method in higher dimensions (n%3E1). Of course, in programming languages like Matlab there are lots of built in optimization routines that work with user specified objective functions and that will be more accurate and faster than what you are likely to program yourself. In Matlab I would suggest using fminsearch or lsqcurvefit.

Edit: The differential equation can be solved either numerically or analytically. Typically, analytical solutions do not exist and numerical solutions are the best we can do.

Jos van Kan · Answer

There is no “best” algorithm. Everything depends on your needs and the nature of the problem. Do you want a surefire convergent algorithm? Do you want a fast algorithm? Unfortunately you can’t have both. On one end of the spectrum you have the “homotopy” method. Say you want to solve [math]G(x)=0, G:\mathbb R^n\to\mathbb R^n.[/math] You have no idea, but you know how to solve [math]F(x)=0, F: \mathbb R^n\to\mathbb R^n.[/math] Subsequently you consider the problem [math]\lambda F(x)- (1-\lambda)G(x)=0,[/math] which you know how to solve for [math]\lambda=1.[/math] Take this as initial estimate for a small decrement in [math]\lambda[/math] and solve with an iterative method of choice. Follow this with small decrements in [math]\lambda[/math] and if there is a path in [math]\mathbb R^n[/math] towards the solution of your problem the homotopy method will find it. This is fairly time consuming.

On the other side of the spectrum you have Newton's method. Starting from an initial guess [math]x_0[/math]

[math]1.[/math] Solve [math]G\ ’(x_k)c_k=-G(x_k)[/math]

2. Let [math]x_{k+1}= x_k+c_k[/math]

to get to the next [math]x_k.[/math] The initial guess has to be (quite) accurate except for monotone problems. Otherwise Newton guides you to a random walk in [math]\mathbb R^n.[/math]

But the homotopy method can serve to get to a fairly accurate estimate after which Newton can take over.

On the other side of the spectrum you have Newton's method. Starting from an initial guess [math]x_0[/math]

[math]1.[/math] Solve [math]G\ ’(x_k)c_k=-G(x_k)[/math]

2. Let [math]x_{k+1}= x_k+c_k[/math]

to get to the next [math]x_k.[/math] The initial guess has to be (quite) accurate except for monotone problems. Otherwise Newton guides you to a random walk in [math]\mathbb R^n.[/math]

But the homotopy method can serve to get to a fairly accurate estimate after which Newton can take over.

Glen Reese · Answer

It is routine to simulate such systems by numerical integration of the equations, to map out their behavior under evolution of the independent variables.

For a simple differential equation of, say, a harmonic oscillator, one method is to plot the the combination of particle position vs velocity, and how this relation evolves over time. This is a phase-space solution.  [ https://www.acs.psu.edu/drussell/Demos/phase-diagram/phase-diagram.html ].

Another famous example is the Lorenz attractor [ https://en.m.wikipedia.org/wiki/Lorenz_system ], which results from the numerical solution of three coupled differential equations representing atmospheric convection. In this cast, the phase space is the combination of convection rate vs, temperature variation, and the phase space diagram shows how this combination of properties evolves over time. This is a famous example of chaotic behavior [ https://en.m.wikipedia.org/wiki/Chaos_theory ], in that the phase-space trajectory never repeats, but wanders around chaotically within certain boundaries.

Alain Debecker · Answer

I once learn a systematic method to solve systems of quadratic equations in n variables. It was meant to study the intersection of two conics.

Unfortunately the computations are so intricate, that I never could use it and always did use adhoc method.

I don't dare to think to what may look like the Cardano formula (cubic equation [ https://en.wikipedia.org/wiki/Cubic_function ]) in two variables. Plus, the Abel–Ruffini theorem [ https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem ] shows there is no solution in the general case if the system is of degree 5 or more.

On the numerical side, the mathematical book Jade Mirror of the Four Unknowns [Zhu Shijie [ https://en.wikipedia.org/wiki/Zhu_Shijie ], 1303 AD] deals with simultaneous equations and with equations of degrees as high as fourteen. He uses a transformation method that he calls fan fa, which looks like a multi-linear extension of the Horner's method [ https://en.wikipedia.org/wiki/Horner's_method ] .

Gil Martins · Answer

It depends on the problem. I really like the “No free launch” theorem. You will have to test and choose, based on the problem.

For black box models you can try Neural Networks (with a non linear activation function) or Non linear SVM (Support Vector Machines)

Gary Ward · Answer

Okay, I think the focus is on computer algorithms that model real physical processes. I can give an example. I have a ship steering console on my porch with a wheel and two engine throttles. I wanted to model actual acceleration where with a change in throttle settings results in a rapid acceleration toward that setting at first and gradually tapers off as speed increases since the energy available for acceleration decreases. The answer was a Bayesian process where current velocity equals current velocity plus percentage of (throttle settings velocity - current velocity). The percentage was really low since the Arduino processor was doing several thousand iterations per second.

So it was the end result that drove the equation creation.

Someone will give a better answer soon.

So it was the end result that drove the equation creation.

Someone will give a better answer soon.

Francesco Romani · Answer

For general linear systems with full coefficiente Matrix, Gaussuan elimination with pivoting or Lu decomposition.

For large sparse linear systems iterative methods exploiting sparsity.

For least squares SVD decomposition sllows some form of regolarization too, in alternative Conjugate Gradient applied to normale equations.

Details can be found on any good Numerical Analysis book.

Anton Mikov · Answer

Depends on whether the system is defined or undefined. Usually, certain systems have a trivial approach to solution.

More interesting and difficult are the indefinite systems, where the numbers of the variables is bigger than the numbers of the equations in the system(s), and the answers (roots) to which can be multiple.

Amar Prasad Rath · Answer

Depends on which kind of programming you are doing.

If you are in application or system programming, where you deal with design of a system or website with given requirements differential equation very rarely used.

In some game design and computer graphics , you might come across a situation where you need to solve a differential equation involving motion.

There is another domain , known as Scientific Computing , where you have to simulate a physical event by numerically solving the differential equation describing their physical behavior. Weather prediction, mechanism simulation, numeric solving requires a lot of knowledge about differential equation, especially Partial Differential Equation(PDE).

John E Pearson · Answer

What Paxson said: numerically. But I would add the following: you should write your differential equations in dimensionless form and then study the resulting system. Say you have dimensionless variables x,y,z and dimensionless “control parameters” A, B, …. Then study the equilibrium solutions x_s, y_s, z_s, … as functions of the control parameters so that x_s=x_s(A,B, …), y_s=y_s(A,B,…) .

Really this is going to depend on your system but if you know where folds in the surface of solutions x_s(A,B,…), y_s(A,B, …), … occur you will at least have the beginning of an idea of the global dynamics the

Really this is going to depend on your system but if you know where folds in the surface of solutions x_s(A,B,…), y_s(A,B, …), … occur you will at least have the beginning of an idea of the global dynamics the system is capable of. I haven’t thought much about this problem for many years but there is a program (named AUTO) written by a Eusebius Doedel that can help you with these issues. Yes. Here it is. AUTO [ http://indy.cs.concordia.ca/auto/ ]

But be forewarned: even fairly simple nonlinear systems can exhibit a bewildering variety of solutions.

Francesco Romani · Answer

In most cases, exact solutions do not exist.

There are a lot of programs that numerically solve this kind of problems but using them requires advanced mathematical skills.