Homework Help Thread - Linear Algebra Edition

[BrotherMan]

Sine! Cosine!
Cosine! Sine!
Three point one
four one five nine!

[Ensign Steve]

Originally Posted by Dragar

So, as I'm a physicist...

Can you think of any physical variables that might be represented by your differential equation?

Um... waves?

Do you mean that equation, specifically?

I'm doing my thesis on nonlinear PDEs, specifically Korteweg–de Vries equation and nonlinear Schrodinger equation. I know what physical phenomena those represent.

(And Deadlokd thought he was joking. )

[Dragar]

Originally Posted by Ensign Steve

Um... waves?

Do you mean that equation, specifically?

I'm doing my thesis on nonlinear PDEs, specifically Korteweg–de Vries equation and nonlinear Schrodinger equation. I know what physical phenomena those represent.

(And Deadlokd thought he was joking. )

Yup, that equation specifically!

Waves is always a good first step, but a wave is a description of a behaviour of a thing, not a thing itself. Your equation is actually a form of a simple harmonic oscillator, one of the most important equations in all of physics. Mainly because almost everything can be approximated to this motion when motions are small.

Your first term - the second derivative - is the acceleration. So that's like the 'force' in F=ma. All the other terms we should think of in terms of forces.

If you had a first derivative, that would act as a damping term; frictional forces are proportional to velocities. Depending on the sign of the coefficient, you could have negative damping, causing a runaway effect - meep!

Then you have a term proportional to y. You have y'' = -y, essentially - so you have a linear restoring force. The further away from y=0, the more you get pushed back to it. This is actually the same force for springs (see Hook's Law), and for pendulums when the motion is small.

Your final term doesn't depend on y - it's a driving force. Your full equation is actually an example of a driven, undamped harmonic oscillator. And you've got two competing frequencies in the system - the natural frequency without the driving force (corresponding the natural swing of a pendulum, or the bounce of a spring) and the frequency of your driving force. (You should write both of these down for your equation and compare!). If the two are very close, you get a resonance effect - like pushing your friend on a swing in time with the natural oscillation of the swing. If the two frequencies are different...well, you can imagine what happens based on your experience with swings, right?

These sorts of equations are found everywhere in physics. Springs, pendulems, electric circuits, quantum mechanics, electromagnetism, particle physics, orbital mechanics, acoustic physics.... and so on. One of my favourite physicists, Sidney Coleman, once described the life of a young theoretical physicist as 'treating the simple harmonic oscillator in ever increasing levels of abstraction'.

If you study Schrodinger's equation, you'll end up studying the quantised version of the harmonic oscillator equation. In fact, you'll see that you can treat any potential well as approximately the harmonic oscillator for small energies.

In fact, modern day particle physics does exactly this - matter is viewed a field, where at each and every point in space there is a simple harmonic oscillator, coupled to all its neighbours (and other fields). That means modern field theory is merely the process of solving an infinite number of coupled, simple harmonic oscillators - and perturbing them slightly outside of that approximation!

So your humble little equation is actually an example of one of the most important equations ever studied. Treat it kindly, study it well!

[Ensign Steve]

Will do!

[Pan Narrans]

Just look at the sign! The sign!!!

[koan]

Why algebra can save you time and money

Proof That Girls Are Evil

[Dragar]

Originally Posted by Pan Narrans

Just look at the sign! The sign!!!

Pff, near enough (though I did misread that!). You can always replace x with ix. It's just a Wick rotation away!

Of course then you have a hyperbolic driving term...

[Ensign Steve]

Guys, help me out with this graph. The vertical axis has a logarithmic scale, and then the curves look like log functions. Does that mean that the curves are actually linear?

From the application, I feel like the blue line is supposed to diverge a hell of a lot from the other two (I figure that's why they used the log scale, otherwise the scale would be too far off to fit all three lines). But if they're all linear, that wouldn't be the case.

What's the significance of the blue line being at 7 when the red and green are at 2? I don't think that means it's 3.5 times bigger. Damn I can't read this shit, it's like the fucking Ricter scale.

[mickthinks]

The curves diverge a lot near the origin, but they seem to become steadier and nearly parallel* for larger values of n, which suggests all 3 functions settle down to an exponential trend.

Log 7 means 107 where Log 2 stands for 102, so the blue process is about 10 000 (105) times slower than the others.

*parallel log means as the three functions increase, they remain in the same approx. 10 000X relation,

[ceptimus]

It doesn't make much difference but beware that MatLab (and Octave) tend to use natural logarithms rather than base-10 ones unless you explicitly write say log10(computationTime) instead of log(computationTime)

With base-10 the logarithm of any number, x, is the power to which 10 must be raised to get x, so log10(100) is 2, log10(1000) is 3 and so on.

Natural logarithms are just the same except that they use e≈2.718281828 instead of 10
log(100) ≈ 4.6, and log(1000) ≈ 6.9

The natural logarithm of a number is always ≈ 2.3 times larger than the log10 of the same number. The exact multiple is just the natural logarithm of 10, log(10) in MatLab.

If you remember that adding logarithms is like multiplying the original numbers that the logs were derived from, you won't go far wrong.

[Ensign Steve]

Awesome, thanks, both of you!

I didn't make the graph, but I'm assuming it's log base-10 from context. But anyway, I don't care about the exact values, so I don't think the base is important. It's more the shape of the curves at that scale that is tripping me up.

Is there anything special about having a log-shaped curve on a logarithmic scale? If one were to "stretch" the graph out so that it was at a linear scale, would those curves straighten up to linear or bend past it to exponential? (I bet if I could remember how to find the derivative of a log function, it would help.)

I think that a linear-looking function on a log scale is really exponential (thanks, mick!) but if the slope was zero, the function would look the same at both linear and log scales, just constant, right? But I guess the question is, what does a linear function look like at a log scale? It looks like a log function, yeah? As the slope of the line decreases, does the function ever "pass through" linear on its way from exponential to constant?

Don't worry if that question makes no sense, it doesn't to me either.

[Ensign Steve]

Oh wait! I got it! Maybe. Here's my question.

All three lines are roughly the same shape, log-shaped, but the blue line has a greater slope. Assuming they approach parallel but never reach it, the blue line will keep diverging a whole lot at the linear scale. Is it possible that the blue line could represent an exponential function while the red and green lines represent linear functions, even though all three are the same shape but with different derivatives?

Edit: just reread this:

Originally Posted by mickthinks

which suggests all 3 functions settle down to an exponential trend.

of course

Here is the thing that is still tripping me up. What happens as the slope of the red and green lines approach zero? Is it still exponential, just a really small exponent? (Is there such a thing? maybe like raising something to the 1.00001 power?)

[SR71]

Do you mean if Y becomes a horizontal asymptote as x increases? In that case you might find the limit and use the limit as an approximation, if you have to fill in numbers? Asymptotes stretch to infinity, and the slope gets incrementally smaller, so I'm not sure if you can ever really nail down a number to use for an exponent.

Sorry if I'm just talking gibberish, I haven't really done any maths in a long time.

[ceptimus]

I scanned the data into Octave and recreated the plot so you can see the original numbers (Octave is like an open-source MatLab, so the same code should run in MatLab, if that's what you're used to).

First here's my plot so you can check it's near enough to your original.



I don't know why the X-axis legend isn't showing "x 10^4" instead of "x 10" - must be some weirdness in the Octave xlabel command - but anyway that's only the legend - the points really are plotted using a x 10^4 scale.

Next, here is the raw data that creates the plot:

#points      ANN time       CUDA time     CUBLAS time

  512         0.00063         0.00063         0.00063

 1024         0.01585         0.00251         0.00200

 2048         0.25119         0.00398         0.00251

 4096         6.30957         0.01000         0.00631

 8192       158.48932         0.06310         0.02512

16384      3981.07171         1.58489         0.50119

32768    158489.31925        19.95262         6.30957

65536   6309573.44480       251.18864       100.00000

and here's the Octave program that has the data, draws the plot and then writes out the data in table form:

clear ; close all; clc;



data = [

#  n   log10(ANN) log10(CUDA) log10(CUBLAS)

  512,   -3.2,      -3.2,        -3.2;

 1024,   -1.8,      -2.6,        -2.7; 

 2048,   -0.6,      -2.4,        -2.6;

 4096,    0.8,      -2.0,        -2.2;

 8192,    2.2,      -1.2,        -1.6; 

16384,    3.6,       0.2,        -0.3;

32768,    5.2,       1.3,         0.8;

65536,    6.8,       2.4,         2.0

];



x = data(:, 1) ./ 1E4;

plot(x, data(:, 2), "-@+b", x, data(:, 3), "-@or", x, data(:, 4), "-@*g"); % ANN, CUDA, CUBLAS);

xlabel('Number of points n X 10^4');

ylabel('Log computation time');

legend('ANN', 'CUDA', 'CUBLAS');



printf("#points      ANN time       CUDA time     CUBLAS time\n");

for i = 1:size(data, 1)

	fprintf("%5d %15.5f %15.5f %15.5f\n", data(i, 1), 10 ^ data(i, 2), 10 ^ data(i, 3), 10 ^ data(i, 4));

end

[Ensign Steve]

You are too awesome, cept! I was 5 minutes away from trying to graph it by hand.

[ceptimus]

From the data you have it looks like CUDA is about two-and-a-half times slower than CUBLAS and ANN is hundreds or thousands of times slower than CUBLAS on the same number of points.

Unless there are some other factors involved, CUBLAS is the winner.

None of them looks like they will scale very well to very much larger data set sizes without taking unfeasibly long run times. Its just possible that the curves might flatten out eventually but it seems unlikely to me based on the data you have. If it were possible to do so, I'd try out just CUBLAS on some bigger data sets to see whether its curve looks like it might ever level out.

[Ensign Steve]

The question is whether CUDA and CUBLAS perform better enough than ANN for it to be worth a shitload of time and money to invest in the switch. I think it does, but I have to justify it.

[mickthinks]

I guess that depends on

1. the current upper limit for n and how long ANN takes to complete the task currently,
2. how often the job needs to be run,
3. and whether and by how much the task is expected to expand in the future

If the job is run once weekly and ANN can do it in 100 hrs, then there's no need to pay a huge premium to have it done by CUBLAS in a few secs*. But if you expect the task to grow in the next few years then ANN might soon need more than a week to run ...

On the other hand, if the process needs to return results every time someone clicks on a website icon then ANN would be no earthly use unless n were guaranteed to remain relatively small.


*BTW I fucked up here - 105 means ANN is in the order of 100 000 times slower, not 10 000 times

[Ensign Steve]

Originally Posted by Ensign Steve

It's not linear algebra, but it's math, so I'm not going to start a new thread.

Oh good, I can still use this one.

I'm not in school, but that doesn't mean I can't have math homework

I have this recursive definition for add:

Add (x, 0) = x
Add (x, S(y)) = S(Add(x,y))

S(x) is essentially x+1, but we haven't defined addition yet, so *hand wave!*

I need to prove that Add is commutative, i.e., Add (a, b) = Add (b, a)

Is that possible to do without Add (0, x) = x in my definition? Is that something that can be derived from my existing definition? ... Now that I type it out loud, that seems like a good place to start.

[Ensign Steve]

Never mind, I did it! I derived a proof for Add (0, x) = x

Then, in typical math student fashion, I said "woohoo! I did it! I proved commutativity! ... oh wait"

Moving on to step 2...

[JoeP]

S(x) probably means "successor", and really what you're proving is that if you already have a function which you call successor which behaves like "the next integer", you can define addition as we know it.

So ... have you completed your proof or is this still a request for help?

[Ensign Steve]

Not done with my proof.

So far I have proved "Add (0, x) = x" and "S(x) = Add (S(0), x)". I'm especially proud of that second one. No more hand wave.

I have also proved "Add (a, S(0)) = Add (S(0), a)".

So I have it proved for base cases b = 0 and b = S(0). I'm using induction, obvs, so I'm currently (so far unsuccessfully) working on how to prove "Add (a, b) = Add (b, a) implies Add (S(a), S(b)) = Add (S(b), S(a))"

Question: Once I get that done, am I done? What of "a"? I can write out the same proof using a instead of b, but how do I know that the proof works for both variables at the same time? If it does at all.

[Ensign Steve]

My tricks so far have been to replace any term S(x) with Add(0, S(x)), and sometimes taking S (or the inverse of S) of both sides. Those moves are all allowed with my current definitions, if unstated here.

[ceptimus]

I think if S(a) has no side effects, also that a, b are distinct then proving that Add(a, b) = Add(b, a) does prove that Add(S(a), S(b)) = Add(S(b), S(a))

You've already proven it for the general case a, b, so it follows that the specific case where a = S(x) and b = S(y) is already proven.

The only remaining problem is the unlikely situation that S(a) doesn't just return a result but affects the original value of a. In C this would be something like:

type S(type *a) { ++(*a) return *a; }

Then Add(S(&a), S(&a)) returns 2a + 3, and leaves a with the value a + 2 - which is, arguably, wrong.

Like I say it's unlikely that S(a) would work like that - in fact to make it work like that in C I had to use pointers to pass the a value to the S() function.

[Ensign Steve]

I don't think I've proved it, though. I proved a couple base cases, but I haven't done the inductive part. I haven't shown that commutativity in the b case implies it for the S(b) case.

I think I got ahead of myself, anyway. I want to prove "Add (a, b) = Add (b, a)". Iterating on b, I can prove "Add (a, 0) = Add (0, a)" and "Add (a, S(0)) = Add (S(0), a)".

I need to prove "Add (a, b) = Add (b, a) implies Add (a, S(b)) = Add (S(b), a)". I got S(a) involved way too early.

Sorry if this reads like crap. Math is impossible on the phone.