using nm to track down the origin of an undefined symbol.

The shared library for our product for historical reasons is built with the (evil) -Bsymbolic flag.

This has a number of unfortunate side effects, one of which is deferring link errors due to unresolved symbols to executable link time, instead of when we build the shared library itself.

Having screwed up in my own build over the weekend, I see a link error in my build summary this morning:

/view/peeterj_m20/vbs/engn/lib/libdb2.so: undefined reference to `XXYY'

I happen to know exactly what caused this (this time), but just the other day I was asked by somebody to help them figure out something similar. So the topic seems worthy of a quick blog post.

Suppose one collects all the archive names that contribute to the shared library in question (for DB2 builders one can relink the library having done an ‘export VERY_VERBOSE=true’ on the command line).

A good way to get this is to redirect that build output to a file, grab just the link line and run something like:

# cat filewithRawLinkLine.txt | tr ' ' '\n' | grep -F -e .a -e .o > archivesAndObjectNames.txt

In my case, this looked like:

# head -5 archivesAndObjectNames.txt    
../../common/crypt/iccsdk/ci_Linux_AMD64/libicc.a     
/view/peeterj_m20/vbs/common/crypt/src/libSTcrypt.a     
/view/peeterj_m20/vbs/common/sdbin/src/libSTdb2sdbin.a     
/view/peeterj_m20/vbs/install/src/libSTjdk_path.a     
/view/peeterj_m20/vbs/engn/atm/alibatm.a     

This now leaves you in the position to search for the archive(s) that contributed the undefined symbol. This can be done with:

# for i in `cat archivesAndObjectNames.txt` ; do echo $i ; nm $i | grep XXYY ; done | tee nm.out | grep -B1 XXYY
 /view/peeterj_m20/vbs/engn/sqe/alibsqe.a        U XXYY

So, the archive supplying a reference to this symbol is ‘alibsqe.a’ This completes the task of doing a first localization of where the link error is coming from. One can continue to do this in a brute force way finding the object file within the archive, or solve it by source inspection once one knows where to look a bit better. In an extremely large source base, where nobody really knows any sizeable portion of it, narrowing down the problem is often an important first step.

Cheating header file dependencies with touch and checkin -ptime.

In our build (DB2) we have some header files, that if changed will result in thousands of source files being recompiled. Sometimes you make a change to a header that you know doesn’t really require rebuilding everything. One way of cheating the build dependency system is to judiciously use the touch command to force the date backwards, as in

touch -t197301010000 /vbs/engn/include/sqleSmartArrayDefines.h
cleartool checkin -nc -ptime /vbs/engn/include/sqleSmartArrayDefines.h

An ls -l command after this will show the file time ’1973-01-01′ (somewhat arbitrarily picked). Thirty five years or so should be early enough to not have make notice it;)

Since we use clearcase for our version control, a checkin of the file into your working branch will change the timestamp unless the -ptime option is used. Care has to be required if you are going to cheat, but I’ve seen people turning off all dependency checking in their build to try to avoid full builds after touching headers, so selecting cheating in a controlled fashion if you are going to do it is a much better option.

Another handy way to do this sort of cheating is ‘touch –reference’. This is a gnu-touch specific (ie: works on Linux) option, that allows you to specify the timestamp using a file instead of a hardcoded date, so you can match the file modification time to some previous point.

Example:

touch --reference sqle_ca_smart_array_cmd.h@@/main/temp_peeterj_db2_galileo_defect_saDeleteDebug/2 sqle_ca_smart_array_cmd.h

In this example, the checked out version (from clearcase) was touched to the predecessor version timestamp after making a change to just a comment that I didn’t want to rebuild everything for.

stripping color control characters from lssam output.

There’s probably a billion ways to do this, but here’s one that appears to work.  If you have TSA command output that has been collected by a somebody who did not use the –nocolor option.

perl -p -e 's/\x1b\[\d+m//g;' < lssamBEFORE.out

The \x1b is the ESC character.  This says to remove that ESC followed by a ‘[‘ character, then 1 or more digits and the character ‘m’, and do it for all lines.

A matrix algebra attack on the multiple mass spherical pendulum problem. (revised)

In a previous post, I’d posted the abstract and intro for a multiple mass spherical pendulum Lagrangian evaluation, along with the full pdf version of those notes.

Having noticed some typesetting bugs (braces missing after the conversion from the original Geometric Algebra version on the same topic), I’ve now posted an update. Again, it is only in pdf, since my latex to wordpress script still needs to be taught how to deal with numbering ‘subequation’s. Now also included is a summary of the equations since it was hard to see what the results and definitions were after the mess of all the algebra.

vim: filtering a function body through a script

While working in a coworker’s cubicle today, I casually ran the following from my vim command prompt

:,/^}/!pdcode -i 1 -s 1

I got a “whoa, what the hell was that” in response, since it was apparently not obvious. There’s really three parts to this. The first is a range expression. In vim (or vi) one can run a command on some set of lines. For example, to delete lines 4 to 8 one would do:

:4,8 d

or to delete 4 lines starting from the current position you could do (without knowing your line number)

:,+4 d

The comma by itself essentially means the current line number, so this is a starting line number of the current spot continuing for 4 additional lines down.

Now, part of the power of the line selection is the fact that one can use search expressions instead of numbers. So, I can run something like:

:,/^}/ d

and this will delete all the lines until the first line that starts with a ending curly brace. The ^ (carat) symbol is a special regular expression indicating the begining of the line, so /^}/ would not match a line that happened to have a brace somewhere else as in the following example.

if ( blah ) { }

Next ingredient is the ! (exclaimation). This says to take the selected lines and pipe them through a filter (something that takes stdin and produces modified stdout, such as grep). In my case, the script was ‘pdcode -i 1 -s 1′. This happens to be a little script I wrote, and it takes all lines like

pdTraceCodePath( 10 ) ;

in a function and renumbers them using the desired step and increment size. For reference this pdTraceCodePath is an internal db2 trace macro that we have that just adds a bit in a 64-bit word, so that later if we want a tracer of the codepath taken (all the branches) we can just dump out this single bitmask and know what the program flow was.

Newton’s method for intersection of curves in a plane.

[Click here for a PDF of this post with nicer formatting]Note that this PDF file is formatted in a wide-for-screen layout that is probably not good for printing.

Motivation.

Reading the blog post Problem solving, artificial intelligence and computational linear algebra some variations of Newton’s method for finding local minumums and maximums are given.

While I’d seen the Hessian matrix eons ago in the context of back propagation feedback methods, Newton’s method itself I remember as a first order root finding method. Here I refresh my memory what that simpler Newton’s method was about, and build on that slightly to find the form of the solution for the intersection of an arbitrarily oriented line with a curve, and finally the problem of refining an approximation for the intersection of two curves using the same technique.

Root finding as the intersection with a horizontal.

Refining an approximate horizontal intersection.

The essence of Newton’s method for finding roots is following the tangent from the point of first guess down to the line that one wants to intersect with the curve. This is illustrated in figure (\ref{fig:newtonsIntersectionHorizontal}).

Algebraically, the problem is that of finding the point , which is given by the tangent

Rearranging and solving for , we have

If one presumes convergence, something not guarenteed, then a first guess, if good enough, will get closer and closer to the target with each iteration. If this first guess is far from the target, following the tangent line could ping pong you to some other part of the curve, and it is possible not to find the root, or to find some other one.

Intersection with a line.

Refining an approximation for the intersection with an arbitrarily oriented line.

The above pictorial treatment works nicely for the intersection of a horizontal line with a curve. Now consider the intersection of an arbitrarily oriented line with a curve, as illustrated in figure (\ref{fig:newtonsIntersectionAnyOrientation}). Here it is useful to setup the problem algebraically from the begining. Our problem is really still just that of finding the intersection of two lines. The curve itself can be considered the set of end points of the vector

for which the tangent direction vector is

The set of points on this tangent, taken at the point , can also be written as a vector, namely

For the line to intersect this, suppose we have one point on the line , and a direction vector for that line . The points on this line are therefore all the endpoints of

Provided that the tangent and the line of intersection do in fact intersect then our problem becomes finding or after equating 3.5 and 3.6. This is the solution of

Since we don’t care which of or we solve for, setting this up as a matrix equation in two variables isn’t the best approach. Instead we wedge both sides with (or ), essentially using Cramer’s method. This gives

If the lines are not parallel, then both sides are scalar multiples of , and dividing out one gets

Writing out , explicitly, this is

Further, dividing out the common bivector, we have a ratio of determinants

The final step in the solution is noting that the point of intersection is just

and in particular, the coordinate of this is the desired result of one step of iteration

This looks a whole lot different than the original for the horizontal from back at 2.2, but substitution of , and , shows that these are identical.

Intersection of two curves.

Can we generalize this any further? It seems reasonable that we would be able to use this Newton’s method technique of following the tangent to refine an approximation for the intersection point of two general curves. This is not expected to be much harder, and the geometric idea is illustrated in figure (\ref{fig:newtonsIntersectionTwoCurves})

Refining an approximation for the intersection of two curves in a plane.

The task at hand is to setup this problem algebraically. Suppose the two curves , and are parameterized as vectors

Tangent direction vectors at the point are then

The intersection of interest is therefore the solution of

Wedging with one of tangent vectors or provides our solution. Solving for this is

To finish things off, we just have to calculate the new coordinate on the line for this value of , which gives us

It is ironic that generalizing things to two curves leads to a tidier result than the more specific line and curve result from 3.13. With a substitution of , and , we once again recover the result 2.2, for the horizontal line intersecting a curve.

Followup.

Having completed the play that I set out to do, the next logical step would be to try the min/max problem that leads to the Hessian. That can be for another day.

Notes on Goldstein’s Routh’s procedure (continued again.)

[Click here for a PDF of this post with nicer formatting]Note that this PDF file is formatted in a wide-for-screen layout that is probably not good for printing.

This continues the Routhian procedure notes from last post.

Polar form example.

The troubles appear to come from when there is a velocity coupling in the Kinetic energy term. Let’s try one more example with a simpler velocity coupling, using polar form coordinates in the plane, and a radial potential. Our Lagrangian, and conjugate momenta, and Hamiltonian, respectively are

Evaluation of the Euler-Lagrange equations gives us the equations of motion

Evaluation of the Hamilitonian equations , should give the same results. First for this gives

The first just defines the canonical momentum (in this case the linear momentum for the radial aspect of the motion), and the second after some rearrangement is

which is consistent with the Lagrangian approach. For the evaluation of the Hamiltonian equations we get

The first again, is implicitly, the definition of our canonical momentum (angular momentum in this case), while the second is the conservation condition on the angular momentum that we expect associated with this ignorable coordinate. So far so good. Everything is as it should be, and there’s nothing new here. Just Lagrangian and Hamiltonian mechanics as usual. But we have two independently calculated results that are the same and the Routhian procedure should generate the same results.

Now, on to the Routhian. There we have a Hamiltionian like sum of terms over all cyclic coordinates, minus the Lagrangian. Here the coordinate is observed to be that cyclic coordinate, so this is

Now, this Routhian can be written in a few different ways. In particular for the dependent term of the kinetic energy we can write

Looking at the troubles obtaining the correct equations of motion from the Routhian, it appears likely that this freedom is where things go wrong. In the Cartesian coordinate description, where there was no coupling between the coordinates in the kinetic energy we had no such freedom. Looking back to Goldstein, I see that he writes the Routhian in terms of a set of explicit variables

where were the cyclic coordinates. Additionally, taking the differential he writes

with sums implied in the second total differential. It was term by term equivalence of these that led to the Routhian equivalent of the Euler-Lagrange equations for the non-cyclic coordinates, from which we should recover the desired equations of motion. Notable here is that we have no for any of the cyclic coordinates .

For this planar radial Lagrangian, it appears that we must write the Routhian, specifically as , so that we have no explicit dependence on the radial conjugate momentum. That is

As a consequence of 4.39 we should recover the equations of motion by evaluating , and doing so for 4.41 we have

Good. This agrees with our result from the Lagrangian and Hamiltonian formalisms. On the other hand, if we evaluate this variational derivative for

something that is formally identical, but written in terms of the “wrong” variables, we get a result that is in fact wrong

Here the term that comes from the dependent part of the Kinetic energy has an incorrect sign. This was precisely the problem observed in the initial attempt to work the spherical pendulum equations of motion starting from the Routhian.

What variables to use to express the equations is a rather subtle difference, but if we do not get that exactly right the results are garbage. Next step here is go back and revisit the spherical polar pendulum and verify that being more careful with the variables used to express allows the correct answer to be obtained. That exersize is probably for a different day, and probably a paper only job.

Now, I note that Goldstein includes no problems for this Routhian formalism now that I look, and having worked an example successfully and seeing how we can go wrong, it is not quite clear what his point including this was. Perhaps that will become clearer later. I’d guess that some of the value of this formalism could be once one attempts numerical solutions and finds the cyclic coordinates as a result of a linear approximation of the system equations around the nieghbourhood of some phase space point.

Notes on Goldstein’s Routh’s procedure (continued)

[Click here for a PDF of this post with nicer formatting]Note that this PDF file is formatted in a wide-for-screen layout that is probably not good for printing.

This continues the Routhian procedure notes started previously.

Now, Goldstein defines the Routhian as

where the index is summed only over the cyclic (ignorable) coordinates. For this spherical pendulum example, this is , and , for

Now, we should also have for the non-cyclic coordinates, just like the Euler-Lagrange equations

Evaluating this we have

It would be reasonable now to compare this the Euler-Lagrange equations, but evaluating those we get

Bugger. We’ve got a sign difference on the term? But I don’t see any error made.

Simpler planar example.

Having found an inconsistency with Routhian formalism and the concrete example of the spherical pendulum which has a cyclic coordinate as desired, let’s step back slightly, and try a simpler example, artificially constructed

Our Hamiltonian and Routhian functions are

For the non-cyclic coordinate we should have

which is

Okay, good, that’s what is expected, and exactly what we get from the Euler-Lagrange equations. This looks good, so where did things go wrong in the spherical pendulum evaluation.

References

[1] H. Goldstein. Classical mechanics. Cambridge: Addison-Wesley Press, Inc, 1st edition, 1951.

Notes on Goldstein’s Routh’s procedure (setup).

[Click here for a PDF of this post with nicer formatting]Note that this PDF file is formatted in a wide-for-screen layout that is probably not good for printing.

Motivation.

Attempting study of [1] section 7-2 on Routh’s procedure has been giving me some trouble. It wasn’t “sinking in”, indicating a fundamental misunderstanding, or at least a requirement to work some examples. Here I pick a system, the spherical pendulum, which has the required ignorable coordinate, to illustrate the ideas for myself with something less abstract.

Guts

The Lagrangian for the pendulum is

and our conjugate momenta are therefore

That’s enough to now formulate the Hamiltonian , which is

We’ve got the ignorable coordinate here, since the Hamiltonian has no explicit dependence on it. In the Hamiltonian formalism the constant of motion associated with this comes as a consequence of evaluating the Hamiltonian equations. For this system, those are

Or, explicitly,

The second of these provides the integration constant, allowing us to write, . Once this is done, our Hamiltonian example is reduced to one complete set of conjugate coordinates,

Goldstein notes that the behaviour of the cyclic coordinate follows by integrating

In this example , so this is really just one of our Hamiltonian equations

Okay, good. First part of the mission is accomplished. The setup for Routh’s procedure no longer has anything mysterious to it. Next step for another day.

References

[1] H. Goldstein. Classical mechanics. Cambridge: Addison-Wesley Press, Inc, 1st edition, 1951.