COMMENT ⊗   VALID 00021 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.require "setup.abs[bib,csr]" source file
C00004 00003	.begin center
C00007 00004	.begin nofill
C00013 00005	.begin nofill
C00019 00006	.begin nofill
C00021 00007	.begin nofill
C00023 00008	.begin nofill
C00029 00009	.begin nofill
C00031 00010	.begin nofill
C00033 00011	.begin nofill
C00034 00012	.begin nofill
C00038 00013	.begin nofill
C00043 00014	.begin nofill
C00044 00015	.begin nofill
C00047 00016	.begin nofill
C00050 00017	.begin nofill
C00054 00018	.begin nofill
C00056 00019	.begin nofill
C00058 00020	.begin nofill
C00061 00021	. <<SOL reports>>
C00074 ENDMK
C⊗;
.require "setup.abs[bib,csr]" source file;
.at "⊗" ⊂"%5αQ%*"⊃
.at "!!" txt ";"	⊂
.("txt"[1]&"∩[%2"&"txt"[2]&"]&∪[ "&"txt"[3]&"]");
.  ⊃
.begin center
S T A N F O R D   U N I V E R S I T Y
MOST RECENT COMPUTER SCIENCE REPORTS - 1979
.end

No. 5↔August

@Listed here are abstracts of the most recent reports published by the
Department of Computer Science at Stanford University.

@TO REQUEST REPORTS:  Check the appropriate places on the enclosed order
form, and return the entire order form page (including mailing label) by
October 26, 1979.  In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first serve basis.  If the code
(FREE) is printed on your mailing label, you will not be charged for hardcopy.
This exemption from payment is limited primarily to libraries.  (The costs
shown include all applicable sales taxes.  PLEASE SEND NO MONEY NOW, WAIT UNTIL 
YOU GET AN INVOICE.)

@ALTERNATIVELY:  Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after the MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL
INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161.
Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North
Zeeb Road, Ann Arbor, Michigan 48106.

@PLEASE NOTE:  In an effort to cut our costs so that we may continue to publish
Stanford Computer Science Reports, we will be making a format change.  Reports
over 100 pages in length will have their page size reduced so that 4 pages can
be printed on 1 sheet of paper.
.next page
.begin nofill
AIM-328↔(STAN-CS-79-743)
@"GOAL:  A Goal Oriented Command Language for Interactive Proof Construction"
Author:  Juan B. Bulnes-Rozas↔(Thesis)
175 pages↔Available in microfiche only.
.end

@This thesis represents a contribution to the
development of practical computer systems for interactive construction of
formal proofs. 
Beginning with a summary
of current research in automatic theorem proving,
goal oriented systems, proof checking, and program verification,
this work aims at bridging the gap between proof checking and theorem proving.

@Specifically,
it describes a system GOAL for the First Order Logic proof checker FOL.
GOAL helps the user of FOL in the 
creation of long proofs in
three ways: 1) as a facility for structured, top down proof
construction; 2) as a semi-automatic theorem prover; and
3) as an extensible environment for the programming of
theorem proving heuristics.

@In GOAL, the user defines top level goals. These are 
then recursively decomposed into subgoals.
The main part of
a goal is a well formed formula that one desires to prove, but they
include assertions, simplification sets, and other information.
Goals can be tried by three different types of elements: 
%2matchers%1, %2tactics%1, and %2strategies%1. 

@The %2matchers%1 attempt to prove a goal directly -that is without
reducing it into subgoals- by calling decision
procedures of FOL. Successful application of a matcher  causes
the proved goal to be added to the FOL proof.

@A %2tactic%1 reduces a goal into one or more subgoals. Each tactic
is the inverse of some inference rule of FOL; the goal structure
records all the necessary information so that the appropriate inference
rule is called when all the subgoals of a goal
are proved. In this way the goal tree unwinds automatically, producing
a FOL proof of the top level goal from the proofs of its
leaves.

@The %2strategies%1 are programmed sequences of applications of tactics and 
matchers. They do not interface with FOL directly.
Instead, they simulate a virtual user of FOL.
They can call the tactics, matchers, other strategies, or
themselves recursively.
The success of this approach to theorem proving
is documented by one heuristic strategy that has proved a number
of theorems in Zermelo-Fraenkel Axiomatic Set Theory.
Analysis of this strategy leads to a discussion of some trade offs
related to the use of %2assertions%1 and %2simplification sets%1 in
goal oriented theorem proving.

@The user can add new tactics, matchers, and strategies to GOAL. These
additions cause the language to be extended in a uniform way.
The description of new strategies is
done easily, at a fairly high level, and no faulty
deduction is possible.
Perhaps the main contribution of GOAL is
a high level environment for easy programming of
new theorem proving applications in the First Order Predicate Calculus.
.next page
@The thesis ends with 
two appendixes presenting complete proofs of Ramsey's theorem in axiomatic Set
Theory and of the correctness of the Takeuchi function.

@(It is planned that both FOL and GOAL will be made available over
the ARPANET this year. Inquiries regarding their use should be addressed
to Dr. R. Weyhrauch at the Stanford Artificial Intelligence Laboratory,
SU-AI).
.next page
.begin nofill
STAN-CS-79-744↔(CSL TR-172)
@"Performance of Update Algorithms for Replicated Data in a Distributed Database"
Author:  Hector Garcia-Molina↔(Thesis)
320 pages↔Cost:  $6.20
.end

@In this thesis we study the performance of update algorithms for replicated
data in a distributed database.  In doing so, we also investigate several other
related issues.

@We start by presenting a simple model of a distributed database which is
suitable for studying updates and concurrency control.  We also develop a
performance model and a set of parameters which represent the most important
performance features of a distributed database.

@The distributed database models are used to study the performance of update
algorithms for replicated data.  This is done in two steps.  First the algorithms
are analyzed in the case of completely replicated databases in a no failure,
update only environment.  Then, the restrictions that we made are eliminated one
at a time, and the impact on the system performance of doing this is evaluated.
For the first step, we develop a new technique for analyzing the performance of
update algorithms.  This iterative technique is based on queueing theory.
Several well known update algorithms are analyzed using this technique.  The
performance results are verified through detailed simulations of the algorithms.
The results show that centralized control algorithms nearly always perform
better than the more popular distributed control algorithms.  This is a surprising
result because the distributed algorithms were thought to be more efficient.

@The performance results are also useful for identifying the critical system
resources.  This insight leads to the development of several new update algorithms
with improved performance.  In particular, the MCLA-h algorithms which we
present performs better than all other update algorithms in most cases of interest.
The MCLA-h algorithm is based on the new concept that "hole lists" which are
used to increase the parallelism of updates.  Several varations of the MCLA-h
algorithms are also analyzed.

@In order to investigate the validity of our results in a general system, we relax
the assumptions made initially in the performance studies.  We show that it is
@possible to make a centralized control algorithm (like the MCLA-h) resilient in
the face of many types of failures.  We show that the cost in terms of performance
for doing this is roughly the same for all algorithms and thus, the original
performance comparisons are still valid in the case of crash resistant algorithms.

@We analyze distributed databases with partitioned data and multiple independent
control mechanisms (called controllers).  We describe transaction processing
in this environment and we discuss how the performance results of the fully
duplicated case can be used to design update algorithms in this environment.
.next page
@We demonstrate how updates that do not specify their base set initially can be
processed.  We present three fundamental alternatives for processing these
updates and we analyze their performance.

@The operation of read only transactions (queries) and their interaction with
the update algorithms has not been covered in the literature.  In this thesis,
we classify queries to free, consistent and current queries, and we present
algorithms for processing each type of query under the different update
algorithms.
.next page
.begin nofill
STAN-CS-79-745
@"Upper and Lower Bounds on Time-Space Tradeoffs in a Pebble Game"
Author:  Thomas Lengauer↔(Thesis)
83 pages↔Cost:  $4.05
.end

@We derive asymptotically tight time-space tradeoffs for pebbling three
different classes of directed acyclic graphs.  Let %2N%1 be the size of
the graph, %2S%1 the number of available pebbles, and %2T%1 the time
necessary for pebbling the graph.

@(a)  A time-space tradeoff of the form 
.skip 3
is proved for pebbling (using only black pebbles) a special class of
permutation graphs that implement the bit reversal permutation.  If
we are allowed to use black and white pebbles the time-space tradeoff
is shown to be of the form
.skip 3
@(b)  A time-space tradeoff of the form
.skip 3
is proved for pebbling a class of graphs constructed by stacking 
superconcentrators in series.  This time-space tradeoff holds whether we
use only black or black and white pebbles.

@(c)  A time-space tradeoff of the form
.skip 3
is proved for pebbling general directed acyclic graphs with only black or
black and white pebbles.
.next page
.begin nofill
STAN-CS-79-746
@"ThingLab -- A Constraint-Oriented Simulation Laboratory"
Author:  Alan Borning↔(Thesis)
109 pages↔Available in microfiche only.
.end

@ThingLab is a system that provides an object-oriented environment for building
simulations.  Within this environment, part-whole and inheritance hierarchies
are used to describe the structure of a simulation, while constraints are employed
as a way of describing the relations among its parts.

@One of the principal goals of this research has been to design and implement a
language that helps the user describe complex simulations easily.  Constraints are
a particularly important tool for dealing with complexity, because they allow the
user to specify independently all the relations to be maintained, leaving it up to
the system to plan exactly how the constraints are to be satisfied.

@ThingLab is implemented in the Smalltalk-76 programming language, and runs
on a personal computer.  Among the things that have been simulated using the
system are constrained geometric objects, a bridge under load, electrical circuits,
documents with constraints on their layout and content, and a graphical
calculator.
.next page
.begin nofill
AIM-329↔(STAN-CS-79-747)
@"Using Patterns and Plans to Solve Problems and Control Search"
Author:  David Edward Wilkins↔(Thesis)
264 pages↔Cost:  $9.10
.end

@The type of reasoning done by human chess masters has not been done by
computer programs.  The purpose of this research is to investigate the
extent to which knowledge can replace and support search in selecting a
chess move and to delineate the issues involved.  This has been carried
out by constructing a program, PARADISE (PAttern Recognition Applied to
DIrecting SEarch), which finds the best move in tactically sharp middle
game positions from the games of chess masters.

@PARADISE plays chess by doing a large amount of static, knowledge-based
reasoning and constructing a small search tree (tens or hundreds of nodes)
to confirm that a particular move is best, both characteristics of human
chess masters.  A "Production-Language" has been developed for expressing
chess knowledge in the form of productions, and the knowledge base
contains about 200 productions written in this language.  The actions of
the rules post concepts in the data base while the conditions match
patterns in the chess position and data base.  The patterns are complex to
match (search may be involved).  The knowledge base was built
incrementally, relying on the system's ability to explain its reasoning
and the ease of writing and modifying productions.  The productions are
structured to provide "concepts" to reason with, methods of controlling
pattern instantiation, and means of focusing the system's attention on
relevant parts of the knowledge base.  PARADISE knows why it believes its
concepts and may reject them after more analysis.

@PARADISE uses its knowledge base to control the search, and to do a static
analysis of a new position which produces concepts and plans.  Once a plan
is formulated, it guides the tree search for several ply by focussing the
analysis at each node on a small group of productions.  Expensive static
analyses are rarely done at new positions created during the search.
Plans may be elaborated and expanded as the search proceeds.  These plans
(and the use made of them) are more sophisticated than those in previous
AI systems.  Through plans, PARADISE uses the knowledge applied during a
previous analysis to control the search for many nodes.

@By using the knowledge base to help control the search, PARADISE has
developed an efficient best-first search which uses different strategies
at the top level.  The value of each move is a range which is gradually
narrowed by doing best-first searches until it can be shown that one move
is best.  By using a global view of the search tree, information gathered
during the search, and information produced by static analyses, the
program produces enough terminations to force convergence of the search.
PARADISE does not place a depth limit on the search (or any other
artificial effort limit).  The program incorporates many cutoffs that are
not useful in less knowledge-oriented programs (e.g., restrictions are
placed on concatenation of plans, accurate forward prunes can be made on
the basis of static analysis results, a causality facility determines how
a move may affect a line already searched using patterns generated during
the previous search).
.next page
@PARADISE has found combinations as deep as 19 ply and performs well when
tested on 100 standard problems. The modifiability of the knowledge base
is excellent.  Developing a search strategy which converges and using a
large knowledge base composed of patterns of this complexity to achieve
expert performance on such a complex problem is an advance on the state of
the art.
.next page
.begin nofill
STAN-CS-79-748
@"Fast Algorithms for Solving Toeplitz System of Equations and Finding Rational 
@Hermite Interpolants"
Author:  David Y. Y. Yun
9 pages↔Cost:  $1.95
.end

@We present a new algorithm that reduces the computation for solving a Toeplitz
system to %2O(n log↑2 n)%1 and automatically resolves all degenerate cases of
the past.  Our fundamental results show that all rational Hermite interpolants,
including Pad%6'%1e approximants which is intimately related to this solution
process, can be computed fast by an Euclidean algorithm.  In this report we
bring out all these relationships with mathematical justifications and mention
important applications including decoding BCH codes.
.next page
.begin nofill
HPP-79-17↔(STAN-CS-79-749)
@"Applications-oriented AI Research:  Education"
Authors:  William J. Clancey, James S. Bennett, and Paul R. Cohen
60 pages↔Available in microfiche only.
.end

@This report is the section from the Handbook of Artificial Intelligence
dealing with research on AI applications in education, the field called
"intelligent computer-assisted instruction" or ICAI.  The Handbook is a
compendium of articles about AI ideas, techniques, and systems and is
intended for the non-AI scientist, engineer, or student.  The material
in this report reviews the historical development of ICAI research and
discusses the important design issues for these systems.  Additional
articles describing the following important ICAI systems are also
included: SCHOLAR, WHY, SOPHIE, WEST, WUMPUS, BUGGY, and EXCHECK.  The
Handbook will be published early in 1980.  We have distributed this
manuscript before publication with the hope of obtaining comments and
suggestions from the AI community.
.next page
.begin nofill
STAN-CS-79-750
@"Khachian's Algorithm for Linear Programming"
Authors:  Peter G%6'%1acs and Laszlo Lov%6'%1asz
12 pages↔Cost:  $2.10
.end

@l. G. Khachian's algorithm to check the solvability of a system of linear
inequalities with integral coeficients is described.  The running time of
the algorithm is polynomial in the number of digits of the coefficients.
It can be applied to solve linear programs in polynomial time.
.next page
.begin nofill
AIM-330↔(STAN-CS-79-751)
@"The Modal Logic of Programs"
Authors:  Zohar Manna and Amir Pnueli
36 pages↔Cost:  $2.75
.end

@We explore the general framework of Modal Logic and its applicability to program
reasoning.  We relate the basic concepts of Modal Logic to the programming
environment:  the concept of "world" corresponds to a program state, and the
concept of "accessibility relation" corrsponds to the relation of derivability
between states during execution.  Thus we adopt the Temporal interpretation
of Modal Logic.  The variety of progrmm properties expressible within the modal
formalism is demonstrated.

@The first axiomatic system studied, the %2sometime system%1, is adequate for
proving total correctness and 'eventuality' properties.  However, it is inadequate
for proving invariance properties.  The stronger %2nexttime system %1obtained by
adding the %2next%1 operator is shown to be adequate for invariances as well.
.next page
.begin nofill
STAN-CS-79-752
@"Projected Lagrangian Algorithms for Nonlinear Minimax and %2l%1↓1 Optimization"
Author:  Michael Lockhart Overton↔(Thesis)
164 pages↔Available in microfiche only.
.end

@This thesis presents new algorithms for solving the nonlinear minimax and
%2l%1↓1 optimization problems.  The minimax problem often arises in circuit
design and game theory, while solving the %2l%1↓1 problem is useful in the
robust analysis of experimental data.  Both problems occur in wide varieties
of discrete data approximation problems in the %2l↓∞%1 and %2l%1↓1 norms.
Both the minimax and %2l%1↓1 problems are unconstrained optimization problems
whose objective functions are not differentiable everywhere, and hence cannot
be solved efficiently by standard techniques for unconstrained optimization.

@It is well known that the minimax problem can be transformed into a nonlinearly
constrained optimization problem with one extra variable, where the objective
and constraint functions are continuously differentiable.  This equivalent
problem has special properties which are ignored if solved by a general-purpose 
constrained optimization method.  The algorithm we present exploits the special
structure of the equivalent problem.  A direction of search is obtained at
each iteration of the algorithm by solving an equality-constrained quadratic
programming problem, related to one a projected Lagrangian method might use
to solve an equivalent constrained optimization problem.  Special Lagrange
multiplier estimates are used to form an approximation to the Hessian of the
Lagrangian function, which appears in the quadratic program.  Analytical
Hessians, finite-differencing or quasi-Newton updating may be used in the
approximation of this matrix.  The resulting direction of search is guaranteed
to be a descent direction for the minimax objective function.  Under mild
conditions the algorithms are locally quadratically convergent if analytical
Hessians are used.

@The %2l%1↓1 problem can also be transformed into a nonlinearly constrained
optimization problem, but it involes many extra variables.  We show, however,
how to construct a method closely related to that for the minimax problem which
requires successively solving quadratic programs in the same number of variables
as that of the original problem.  Thus the %2l%1↓1 problem is as tractable as
the minimax problem by the projected Lagrangian technique.

@Because the minimax and %2l%1↓1 objective functions are not necessarily
differentiable along the directions of search, it is important to use special
line search algorithms to obtain reductions in these functions at each
iteration.  Several flexible steplength algorithms are presented, along with
algorithms for univariate minimization of the minimax, %2l%1↓1 and related
objective functions.

@The usefulness of the methods is illustrated by presenting the results of
applying them to a number of problems from the literature.
.next page
.begin nofill
STAN-CS-79-753
@"Should Tables Be Sorted?"
Author:  Andrew Chi-Chih Yao
36 pages↔Cost:  $2.75
.end

@We examine optimality questions in the following information retrieval
problem:  Given a set %2S%1 of %2n%1 keys, store them so that queries of
the form "Is %2x ε S%1?" can be answered quickly.  It is shown that, in
a rather general model including all the comonly-used schemes,
%3i%21g(n+1)%3j%1 probes to the table are needed in the worst case,
provided the key space is sufficiently large.  The effects of smaller
key space and arbitrary encoding are also explored.
.next page
.begin nofill
HPP-79-21↔(STAN-CS-79-754)
@"Natural Language Understanding"
Authors:  Anne Gardner, James Davidson, and Terry Winograd
100 pages↔Available in microfiche only.
.end

@This report is the section on Natural Language research from the
Handbook of Artificial Intelligence.  The Handbook is a compendium of
articles about AI ideas, techniques, and systems intended for non-AI
scientists, engineers, and students.  The material in this report
reviews the development of ideas for computer programs that understand
natural language, briefly sketches the main ideas of several types of
grammars and parsing strategies, and describes, among others, the
following important NL systems: LUNAR, SHRDLU, MARGIE, SAM, PAM, and
LIFER.  The Handbook will be published early in 1980.  We have
distributed this manuscript before publication with the hope of
obtaining comments and suggestions from the AI community.
.next page
.begin nofill
AIM-331↔(STAN-CS-79-755)
@"Efficiency Consideration in Program Synthesis:  A Knowledge-Based Approach"
Author:  Elaine Kant↔(Thesis)
160 pages↔Cost:  $6.20
.end

@This thesis presents a framework for using efficiency knowledge to guide
program synthesis when stepwise refinement is the primary synthesis
technique.  The practicality of the framework is demonstrated via the
implementation of a particular search-control system called LIBRA.  The
framework is also one model for how people write and analyze programs.

@LIBRA complements an interactive program-synthesis project by adding
efficiency knowledge to the basic coding knowledge and by automating the
implementation-selection process.  The program specifications include size
and frequency notes, the performance measure to be minimized, and some
limits on the time and space of the synthesis task itself.  LIBRA selects
algorithms and data representations and decides whether to use
"optimizing" transformations by applying knowledge about time and storage
costs of program components.  Cost estimates are obtained by incremental,
algebraic program analysis.

@Some of the most interesting aspects of the system are
explicit rules about
plausible implementations, constraint setting, multiple-exit-loop
analysis, the comparison of optimistic and achievable cost estimates to
identify important decisions, and resource allocation on the basis of
importance.  LIBRA has automatically guided the construction of programs
that classify, retrieve information, sort, and compute prime numbers.
.next page
.begin nofill
HPP-79-22↔(STAN-CS-79-756)
@"Applications-oriented AI Research:  Science and Mathematics"
Authors:  James S. Bennett, Bruce G. Buchanan, Paul R. Cohen, and Fritz Fisher
110 pages↔Available in microfiche only.
.end

@This report includes material from the Handbook of Artificial
Intelligence covering AI research aimed at applications in various
domains.  The Handbook is a compendium of articles about AI ideas,
techniques, and systems intended for non-AI scientists, engineers, and
students.  The material in this report covers research in applying AI
techniques in systems to be used by chemists, mathematicians, and other
scientists and includes descriptions of programs like TEIRESIAS, AM,
MACSYMA, PROSPECTOR, DENDRAL, CONGEN, Meta-DENDRAL, and CRYSALIS.  The
Handbook will be published early in 1980.  We have distributed this
manuscript before publication with the hope of obtaining comments and
suggestions from the AI community.
.next page
.begin nofill
HPP-79-23↔(STAN-CS-79-757)
@"Applications-oriented AI Research:  Medicine"
Authors:  Victor B. Ciesielski, James S. Bennett, and Paul R. Cohen
40 pages↔Available in microfiche only.
.end

@This report includes material from the Handbook of Artificial
Intelligence describing research on applying AI techniques to medical
systems.  The Handbook is a compendium of articles about AI ideas,
techniques, and systems intended for non-AI scientists, engineers, and
students.  The articles in this report give an overview of research in
AI applications in medicine and describe the following important medical
programs: MYCIN, CASNET, INTERNIST, PIP, Digitalis Advisor, IRIS, and
TEIRESIAS.  The Handbook will be published early in 1980.  We have
distributed this manuscript before publication with the hope of
obtaining comments and suggestions from the AI community.
.next page
.begin nofill
HPP-79-24↔(STAN-CS-79-758)
@"Automatic Programming"
Authors:  Robert Elschlager and Jorge Phillips
100 pages↔Available in microfiche only.
.end

@This report is the section from the Handbook of Artificial Intelligence
on Automatic Programming (AP) research.  The Handbook is compendium of
articles about AI ideas, techniques, and systems intended for non-AI
scientists, engineers, and students.  The material in this report
surveys AP methodologies and program specification techniques and
describes in some detail the following AP systems: PSI, SAFE,
Programmer's Apprentice, PECOS, DAEDALUS, PROTOSYSTEM-I, NLPQ, and
LIBRA.  The Handbook will be published early in 1980.  We have
distributed this manuscript before publication with the hope of
obtaining comments and suggestions from the AI community.
.next page
.begin nofill
HPP-79-25↔(STAN-CS-79-759)
@"Schema-shift Strategies for Understanding Structured Texts in Natural Language"
Author:  Alain Bonnet
40 pages↔Available in microfiche only.
.end

@This report presents BAOBAB-2, a computer  program built upon MYCIN
(ref Shortliffe74) that is used for understanding medical summaries
describing  the status  of patients. Due both to the conventional way 
physicians present medical problems in these summaries and
the  constrained nature  of medical jargon,  these texts  have a very
strong structure.  BAOBAB-2 takes  advantage of  this  structure  by
using a model of this  organization as a set of related schemas that
facilitate  the interpretation  of  these  texts. Structures  of  the
schemas  and their relation  to the surface  structure are described.
Issues relating to selection and  use of these schemas by the program
during interpretation of the summaries are discussed.
.next page
. <<SOL reports>>
.once center
SYSTEMS OPTIMIZATION LABORATORY
.skip
@The following reports are available from the Systems Optimization Laboratory.
SOL Reports can be obtained by writing to:  Gail L. Stein, Systems Optimization
Laboratory, Operations Research Department, Stanford University, Stanford,
California 94305.
.skip 2
.begin nofill
Technical Report SOL 79-5
@"Sparse Least Squares by Conjugate Gradients: A Comparison of Preconditioning 
@Methods"
Author:  Michael A. Saunders
.end

@The conjugate-gradient method is ideal for sparse least squares because of its
simplicity and low storage requirements, and because it can be relied upon to
converge to a satisfactory solution.  However, the number of iterations required
can be unacceptably high if the design matrix X is ill-conditioned.

@In this context, preconditioning means a change of variables aimed at
accelerating convergence.  For some nonsingular C, the usual linear model
%2y = %1X%5b%2 + e%1 is transformed into %2y = %1X%5b%2 + e%1,
where X = XC∩[-1].  (The product is not computed explicitly.)
If X is better conditioned than X, the transformed problem should
require fewer iterations.

@Here we give come computational results for two particular choices of C.
The SSOR approach of Bj%6:%1orck and Elfving promises to give useful savings
generally.  When X is very ill-conditioned, it appears that an LU factorization
of X (with C = U) can lead to even faster convergence.