Confessions of a Naïve Programmer (4)

How I programmed my life.

Matrix — Photo by Markus Spiske on Unsplash

Continued from Part 3.

1.4 Optimal control problem and linear programming

„Your hour has come, the rage of darkness.“ (Lk 22, 53)

Day and night I cry out to you, O Lord. O Lord God, my Savior, I cry out to you day and night. Hear my prayer, listen to my cry for help.

So many troubles have overtaken me, that I am on the threshold of Sheol. People consider me as one destined to go down to the Pit; I am like a man who has no power., (Friday Night Prayer)

It’s time to talk about the main task I developed for the department. In today’s world of copyright, it would be a bold statement that the system I was developing does not belong to me in any way, shape, or form. But we’ll set the copyright dispute aside just long enough to say that, after all these years, I finally have the right to publish its operating principles and source code, not in Fortran, but in ported and slightly reworked code in two languages — C in 1991 and JavaScript in 2018. The original Fortran code was completed in 1977. Now you can imagine the significance of this program for me, stretching like a magical thread through my life to the point of its use as one of the most important test cases for the Memel OS 1 system.

Along the way, using this very program, I effectively disavowed a long-standing taboo and proved that iterative problem-solving algorithms can be programmed to execute in parallel and are 1.5 to 2 times faster than the sequential code. Now I can say outright that I’ve made a discovery — I’ve proven that iterative loops can be successfully parallelized. Since the system’s creation, it has become possible to actually (i.e., literally) demonstrate a parallel software environment that accelerates an iterative problem by a factor of 2 or even more. The method for finding the fastest convergence is called the calculus of variations, which goes very deep — to the roots of all mathematical — and other — sciences.

The variable ‘k’ in the parallel version of my program is this variational variable that controls convergence. Thus, we can run several variations of each iteration in parallel and choose the most accurate one to find the fastest functional of convergence to its local and then — global extremum. I took the formulation of the linear programming problem and its iterative solution from the specialized literature: R. P. Fedorenko, “Approximate Solution of Optimal Control Problems,” Moscow, Nauka Publishing House, 1977, pp. 437–452. A rather complex solution was proposed there, based on the very dark magic of linear algebra. So, I had to study mathematics quite deeply, in the part that concerns discrete and applied mathematics, and, in particular, linear algebra.

As a result, I knew math incredibly well, though not quite what we covered in lectures. The lectures were given by a professor who served as the dean of our course. And just as I was finishing my first topic in the Student Scientific Advisory Service, she failed me on an exam. Approximately 95% of the entire second-year student population failed her exams, and I happily joined them. The reason for this later became clear: the dean’s office, headed by her, simply needed to thin out and move up the dorm line. I quickly realized this when, around New Year’s, right before the holidays, I was politely asked to leave my room and the dorm as a whole.

The exam situation was quickly resolved, but I lost my dorm room because the dean had no idea what I was doing at the Student Scientific Society. I had to quickly look for an apartment and found one in the Pushkinovka area on Subaciaus Street, mostly Polish neighbourhood of Vilnius, where the private sector predominates. Meanwhile, I finally got the first results from my linear programming program. This meant that the program’s creation process was complete, and the equally lengthy and arduous process of debugging and testing was about to begin.

At that time, TDD (Test Driven Development) hadn’t been invented yet (thank goodness), and a program could only be run once a day, or twice if you gave the senior machine operator some candy. These were the options for debugging software systems that existed at the time. Although static analysis tools had already been used in some systems, they were primarily focused on compiler development and critical hardware. Simple scientific programs did not use them.

I realized quite late the role of my part of the system (the linear programming module) in the overall context of the optimal control problem. My supervisor finally decided to share a bit more about the system being developed than before, perhaps because the development of my part was already in the final stage.

So, this is the problem: there is a clamped cantilever beam of a certain stiffness and a spatial load diagram for this beam, as well as the points of maximum stress. Statically, the beam’s clamped point can withstand three times the actual load. The loads (for which the stress diagrams are given) are dynamic and act chaotically, having only a limit (wind simulation). The task consists of finding the eigenvectors of the entire structure, identifying the locations of the diagram’s zero-crossing points, resulting in resonance, which in turn is determined by the eigenvalues ​​of the combined stress matrix. The practical application is the calculated locations of dangerous points of natural oscillations, into which a special material must be inserted to stop or dampen these oscillations. -: end of problem statement.

As far as I understood then, this problem was the topic of his doctoral dissertation, so he spoke about it in very general terms and didn’t reveal the details of his intended solution. I was fortunate enough to see the code for a higher-level optimization program on his desk only once, where my program was simply called from some crazy loop. The next part I was given was the problem of finding the eigenvectors and eigenvalues ​​of an arbitrary matrix. Here I understood why he used an iterative method for solving a system of linear equations, rather than the well-known simplex method.

There were two reasons for this: the original matrix did not change with the iterative method, and as a result, the matrix elements can be simply calculated, which greatly saves memory and allows for static control of larger dimensions of the original matrices and more precise control of the beam stress diagrams. The second reason is that the stress diagrams form tridiagonal matrices, and even at 100x3 dimensions, they bypass the simplex method for using the matrix in computer memory. The iterative method works very well with sparse matrices, which are what the matrices described here are. This is certainly not obvious today, but look back to 1977, when memory capacity was measured in kilobytes (!) and the entire memory of the most advanced BESM-6 was 64 kilowords, doubling only in 1978.

At the moment I came across a book with matrix and vector manipulation algorithms in the Algol-68 programming language. This was my virtual language, which I learned after Fortran and in which I never wrote a single program — I only ported numerous linear algebra algorithms to Fortran. Along the way, I learned all the intricacies of matrix and linear algebra — there simply wasn’t a better textbook! It was a textbook where you take a topic, then port an example from Algol to Fortran, and immediately run it on a computer.

1.5 Illness as a gift from God?

Do you perform miracles for the dead? Will the shadows rise up to praise you?

Will anyone declare your goodness in the grave, or your faithfulness in Abaddon? Are your wonders told in the shadow of death, or your righteousness in the land of oblivion?

But I, O Lord, call upon you; my prayer comes to you every morning. O Lord, why have you cast me off? Why do you hide your face from me?

I have been afflicted from my youth, and I am near death; your terrors overwhelm me.

Your wrath falls upon me, your terrors overwhelm me.

Like a flood they drown me all day long; they surround me on every side. You have removed friends and neighbors from me; darkness surrounds me wherever I am. (Friday Night Prayer — continued)

The paramedics came running and secured us… (V. Vysotsky)

The entire year of 1977 was marked by illness, strange and incomprehensible. First, I moved to a student sanatorium on Olandu Street, where I continued to study at the institute and work at the Student Scientific Society. Since no one could find the cause of my illness, it was assumed there was something wrong with my psyche. Gradually, the illness progressed from acute to chronic. Psychiatrists worked there, establishing me at an optimal level where, although not without difficulties, I could study and work. At this point, I was working on improving and debugging my iterative linear programming system.

The 1991 port of the program to C can be found here (examples/linear-programming/matrix-150x500/linit.c). The 2018 port to JavaScript is here (examples/linear-programming/matrix-150x500/linit.seq.js). The latest version includes macro tags for running it in parallel mode under Memel OS 1 (linit.par.js). This also includes changes to the program layout: the main program has been separated and all functions have been isolated, now consisting of subroutines in the classic (a la dinosaur) style. You can run *.js files directly from this environment by pressing “Run” button and watch results in the console.

Of course, my work at the Academy of Sciences’ computing centre wasn’t limited to just this one program. During my four years there, I created dozens of different programs and used many technologies, including the “Jinn” dialog system running under the “Dubna” monitoring system, the “Benson” graph plotter, and many other available BESM-6 subsystems.

I won’t bore the esteemed public with all the details of my work as a programmer back then, only because I didn’t produce anything “naïve” (contradictory) in programming. Back then, I was just learning to be a programmer making independent decisions.

As for my illness, it developed into a feeling of anxiety, because of which I began to rush to live and therefore sought to try many things in terms of my activities, where I no longer saw myself as anyone else — only a programmer.

To be continued…

Disclaimer: This text is translated from Russian and Lithuanian to English using Google Translate, so please excuse me for sometimes clumsy language, since there is a huge difference in the internal structure between languages.