𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient solution of sparse sets of design equations

✍ Scribed by M.A. Stadtherr; W.A. Gifford; L.E. Scriven

Publisher
Elsevier Science
Year
1974
Tongue
English
Weight
946 KB
Volume
29
Category
Article
ISSN
0009-2509

No coin nor oath required. For personal study only.

✦ Synopsis

A new algorithm is described which can help the engineer find efficient strategies for solving sets of equations of the sorts that arise in process design. The algorithm systematically exploits small subsets of equations that can be solved directly because they are linear in certain variables or can be reduced to solvable forms. Technically a combination of 'partitioning' and 'indexing,' it recognizes that 'tearing' to make the equation set 'triangular' for iteration may not minimize the number of variables which must be iterated, or 'torn'. Requiring only simple matrix rearrangements, the algorithm has been implemented easily by hand for systems of 15 or more equations. It yields improvements in strategies published by Lee et al. and Christensen and thus makes plain the possibility of improving on published precedence-ordering and tearing algorithms for computer-aided design.

πŸ“œ SIMILAR VOLUMES

Errata to β€œefficient approximate solutio
Errata to β€œefficient approximate solution of sparse linear systems” solution of
πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 29 KB

The following changes should be made to the above-mentioned article. ## β€’ Page 45, line 2: replace A = D(A) + A + + A-with A = -D(A) + A + + A-. β€’ Page 48, line 27: replace n' = (n27l'1) 1/w+l with n' = n 1'5. β€’ Page 48, line 30: replace O(n(~r + logn)) ~/~+1 with O(nl"5(lr + logn)). β€’ Page 51, l

On reductions of NP sets to sparse sets
On reductions of NP sets to sparse sets
✍ Steven Homer; Luc LongprΓ© πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 678 KB

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following: β€’ Applications of the main theorem to log-truth-tabl