The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Generalized Nested Dissection
Abstract
J. A. George has discovered a method, called nested dissection, for solving a system of linear equations defined on an $n = k \times k$ square grid in $O(n\log n)$ and space $O(n^{{3 /2}} )$ time. We generalize this method without degrading the time and space bounds so that it applies to any system of equations defined on a planar or almost-planar graph. Such systems arise in the solution of two-dimensional finite element problems. Our method uses the fact that planar graphs have good separators. More generally, we show that sparse Gaussian elimination is efficient for any class of graphs which have good separators, and conversely that graphs without good separators (including “almost all” sparse graphs) are not amenable to sparse Gaussian elimination.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
The finite element method in engineering science
Zienkiewicz, O. C. (1971) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,376
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
A Separator Theorem for Planar Graphs
Lipton, R. J., & Tarjan, R. E. (1979) · SIAM Journal on Applied Mathematics · doi:10.1137/0136016 · Cited by 1,359
Self-citationAlgorithmic Aspects of Vertex Elimination on Graphs
Rose, D. J., Tarjan, R. E., & Lueker, G. S. (1976) · SIAM Journal on Computing · doi:10.1137/0205021 · Cited by 1,203
Self-citationNested Dissection of a Regular Finite Element Mesh
George, A. (1973) · SIAM Journal on Numerical Analysis · doi:10.1137/0710032 · Cited by 1,064
Efficient Algorithms for Shortest Paths in Sparse Networks
Johnson, D. B. (1977) · Journal of the ACM · doi:10.1145/321992.321993 · Cited by 1,041
Computer Solution of Linear Algebraic Systems
H., A. S., Forsythe, G. E., & Moler, C. B. (1970) · Mathematics of Computation · doi:10.2307/2004501 · Cited by 828
Probabilistic Methods in Combinatorics
Spencer, J. (1995) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-9078-6_132 · Cited by 588
Triangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 500
Self-citation
Cited by
iSAM2: Incremental smoothing and mapping using the Bayes tree
Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J. J., & Dellaert, F. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364911430419 · Cited by 1,362
Square Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing
Dellaert, F., & Kaess, M. (2006) · The International Journal of Robotics Research · doi:10.1177/0278364906072768 · Cited by 922
Applications of a Planar Separator Theorem
Lipton, R. J., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209046 · Cited by 640
Self-citationRoute Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_2 · Cited by 610
Metadata
- Authors
- Lipton, R. J., Rose, D. J., & Tarjan, R. E.
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 1979-04
- Volume
- 16
- Issue
- 2
- Pages
- 346-358
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W2113679823
- Cited by
- 560
- References
- 19
- FWCI
- 3.92
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Generalized Nested Dissection. https://app.cochat.ai/papers/10.1137/0716027
- The paper
- Lipton, R. J., Rose, D. J., & Tarjan, R. E. (1979). Generalized Nested Dissection. SIAM Journal on Numerical Analysis. https://doi.org/10.1137/0716027
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
