The matrix stage of integer factorization sieves.
Modern general-purpose methods of integer factorization consist of two major stages: Sieving, and linear algebra. In the sieving stage, a large set of "relations" are produced of the form "product of primes = something squared modulo N" (the number field sieve uses prime ideals in a number field, but the general idea is the same). In the linear algebra stage, a combination of relations is found which, when multiplied together, produces an equation of the form "something squared = something else squared modulo N" -- in other words, all of the primes on the left side of the equation are raised to even powers -- and from this it is easy to find factors of N. The linear algebra stage is so named because finding the correct combination of relations to multiply together is equivalent to solving a large sparse system of linear equations modulo 2.Out of these two stages, the linear algebra is generally considered to be the harder. Whereas the sieving can be distributed across a large number of machines, current methods for solving the sparse linear system (for example, block Lanczos) require tightly-coupled processors: The time taken to solve a matrix with n rows and weight w on a network with interprocessor latency L is O(n w + n L), and with the matrices often having tens of millions of rows, even a network latency of a millisecond will add hours to the computation. Clearly, if the size of the matrix can be reduced via some preprocessing, this will make finding the solution much faster -- as long as the matrix weight doesn't increase too much.
The oldest method for solving systems of linear equations is Gaussian elimination. Find a non-zero element of the matrix, and add multiples of its row to other rows in order to eliminate all the other non-zero entries in the same column. Unfortunately, this naive method results in the weight of the matrix increasing rapidly -- so-called "catastrophic fill-in". A somewhat more intelligent approach called "Structured Gaussian elimination" is also available; in this method, the matrix is split into two parts, labeled as the "dense" and "sparse" parts, and the pivot used is chosen in order to minimize the increase in the weight of the sparse part. This approach also ends up causing rapid matrix fill-in, but at least makes some useful progress first: Depending upon the source of the original matrix, it can often reduce the matrix size by a factor of 10 or more before it reaches the point where continuing would be disadvantageous due to increasing matrix weight. As a result, structured Gaussian elimination is useful as a method of matrix preprocessing, but not as a method of matrix solution.
Now for the interesting question: Why are we trying to eliminate columns at each stage? What if, instead, we view the problem as one of lattice reduction, and add rows to each other not with a view to reducing the number of active columns directly, but instead with the intention of decreasing the matrix weight?
If we consider the rows of the matrix as zero-one vectors, then any time the dot product of two rows is more than half of the number of nonzero entries in the lighter row, we can add the lighter row to the heavier row and reduce the total matrix weight. Instead of taking a row and adding it to all the other rows with nonzero entries in a particular column, just add it to a few other rows -- the ones whereby you can decrease the matrix weight. Of course, this relies upon being able to find rows which are not too close to orthogonal, but there is a good reason to think that they might exist: If two medium-sized primes p and q appear in a relation which is used to eliminate a large prime in several other relations, then unless either of those primes also appeared in the other relations, all of the new relations will contain both of those primes. As a result, groups of primes tend to "stick together", which increases the largest dot products of pairs of rows.
Can this sort of approach provide a significant benefit over existing methods? It's too early to be certain, but on some "toy problems" -- matrices arising from applying the quadratic sieve to 18-digit numbers using a factor base of a few thousand primes -- I found that structured Gaussian elimination ended up with catastrophic fill-in (not that filling in a matrix of a few hundred rows is particularly catastrophic), while this lattice reduction approach steadily reduced the matrix weight.
CBC and CMG reach a tentative deal.
The Canadian Broadcasting Corporation and the Canadian Media Guild have reached an agreement in principle to end the current lockout. I'm not going to recycle news from around the Web, but Tod Maffin of CBCunplugged interviewed one of the CMG's lead negotiators and asked if anyone could produce a transcript of the interview. Without any further ado:Tod Maffin: This is a special edition of CBCunplugged.com, it is late at night on Sunday -- I guess now currently Monday, October the 3rd -- and on the line is Arnold Amber, with the CMG negotiating team. Arnold, you must be exhausted.
Arnold Amber: Sure am. Yesterday, we worked right through until 6AM Sunday morning, were back at it already back across the river in Gatineau at noon, and we finished up now, and I'm just getting back to the Hotel and it's 2 o'clock in the morning. So, a long and hard struggle; many many months.
TM: What comes next; what are the next steps? I know that it is an agreement in principle, so presumably there is still some language text to work out.
AA: First of all, the ceremony: We go back to the mediation services of the Canadian government offices in Gatineau Quebec tomorrow morning; 9:30 we meet with the labour minister under whose auspices the talks these last seven days went on; we then will sign an agreement, a memorandum of agreement; and then we work out perhaps one of the most important things we're going to do over the next little while, and that is the Return To Work protocol -- these are the terms and conditions by which all our members will be reintegrated into the CBC -- and finally, the Canadian Broadcasting Corporation radio, television, and dot-ca will finally be able to restore the services that Canadians have used so widely and of which we heard so much about over the lockout about how much they miss.
TM: What pushed the final moment? Did the guild make an offer, did the labour ministry intervene; what point was the actual tipping point in this tonight?
AA: In my view there were two tipping points. One of them occurred Mon- uh, Wed- uh, sorry, Saturday morning. Saturday morning, when one of the mediators, Don Howard (?), stood up in a meeting, two representatives of the Guild, me and Dan Olsen from the Guild, and two representatives from the CBC and two mediators, him and Elizabeth MacPherson, the head of the mediation services, and he suggested a way that we could overcome two or three issues that still stood out, and drew some things on the board, and from that we rapidly developed a mechanism for moving forward, and although Saturday turned out to be a long hard day, that was the first of many tipping points.
AA: The second point was, there's something that I -- you know, I'm one of the "veteran" if I may put it in slight terms, negotiators with the CBC, in other words, I've done many many years -- but talking to some of the younger folks on this negotiating team, I said "you know, you'll find it very surprising, but until someone says 'yes' across the table, they often say 'no' very loudly and insistently". All the way up until 8:30, 9 o'clock on Sunday, the CBC was holding firm to various things and acting in a very certain way; and finally we exchanged paper. The CBC submitted a list of what it called the "outstanding issues" in the dispute and their positions about them, and they asked us to do the same; and Dan Olsen and I got together and wrote up our paper and submitted it to the CBC, somewhere in the neighbourhood of 9 o'clock. They came back a little after 11, and their response to our paper was very positive. There were two more passes between parties to finally work out all the agreements, and then by about 12:20 Monday morning that was that.
TM: Awesome. Well, I know you're exhausted; I'll let you get some sleep and I really appreciate your time.
AA: Before I do go, I just really think that I have to say two things. The first thing is that this particular dispute has ended now, and what it established beyond a shadow of a doubt is that at the CBC, public broadcasting and Canada's national broadcaster, the Guild has been able to reassert the notion in contract language that a permanent workforce is the heartthrob of the corporation. We have a cap now on the percentage of contract workers that the CBC will be allowed to bring in at 9.5 of the permanent workforce.
AA: The second thing I want to do is say that, to all our members who throughout this lockout worked so hard to get the public involved, to get politicians involved, to created as well incredible imaginative websites, this is a new modern age labour dispute that our members carried out to the fullest. Many people had a great time on the line and did some of the most imaginative and thoughtful things, and it became a work of art, this labour dispute. I thank that all the people for their support, their activity, and we couldn't have gotten at the table what we did without all that help, so I want to thank all of them.
TM: Arnold, what city do you live in, out of curiosity?
AA: I live right now in Toronto.
TM: And when do you think you'll be getting back?
AA: Oh, I think I'll be getting back tomorrow some time. I have a religious holiday on Tuesday, so I'm going to be paying attention to that for once -- it's a burden which has been lifted from our shoulders.
TM: I'll bet. And any idea when a ratification vote will happen?
AA: We have to develop the language which goes with the principles which we've developed, and from there we'll be setting our schedule tomorrow some time.
TM: So, do people still remain picketing until the vote has gone through, or is that still all up in the air?
AA: Yes, they continue picketing for a number of reasons. One of them is that until they're asked to return to work, we're still sort of in this conflict with the CBC, although it's not real. It's going to be funny to say to them to relax the picket lines, because in many cases, in many cities, the picket lines were more like happenings. In Toronto, where I spent some of the time, because we were negotiating down there for quite a while, the picket line was basically a series of marching about but there were concerts, there were Yoga sessions, there were bake-offs, just as there were across the country; but anyways, we're going to tell them to be even more relaxed picketing over the next couple of days.
TM: Well, I can hear in your voice that you're exhausted, you have a number of days before you, and I really do appreciate your time Mr. Amber.
AA: Thank you very much.
TM: Thank you for talking to me.
AA: Goodbye.
TM: Goodbye.
Note: I cleaned up the interview slightly by removing non-words and mis-spoken words which were immediately corrected, and by correcting some grammar. In Arnold Amber's third paragraph, some of the words and especially names were hard to hear, so I may have gotten them wrong -- I apologize in advance to anyone whose name I transcribed or spelt incorrectly.