稀疏线性系统直接求解方法——Timothy A Davis

需积分: 29 169 浏览量更新于2024-07-21 收藏 27.42MB PDF 举报

"《Direct Methods for Sparse Linear Systems》是由Timothy A Davis撰写的一本关于稀疏线性系统直接求解方法的专业教材。该书属于SIAM（美国工业与应用数学学会）的基础算法系列，旨在为读者提供选择合适方法解决特定应用问题的知识，并深入理解每种方法的局限性。书中主要探讨了LU分解法以及对称和非对称求解法，适合研究人员、实践者和学生阅读。" 《Direct Methods for Sparse Linear Systems》这本书深入浅出地介绍了用于解决稀疏线性系统的直接方法。在数值计算领域，稀疏矩阵因其大部分元素为零而具有重要的实际意义，尤其是在大型科学计算和工程问题中。LU分解法是这些方法中的基础，它将一个矩阵分解为一个下三角矩阵L和一个上三角矩阵U，从而简化了求解线性方程组的过程。书中的内容不仅涵盖了LU分解，还讨论了对称和非对称线性系统的求解策略。对于对称问题，Cholesky分解是一种有效的方法，它适用于对称正定矩阵，能进一步减少计算量。而对于非对称问题，QR分解和追赶算法等方法则更为常见，它们在保持数值稳定性的同时，也能处理更广泛的矩阵类型。此外，书中强调了如何根据问题特性选择最佳的算法、软件包或方法，以及如何评估特定算法的成功与否。这种实用导向使得读者不仅能理解算法的工作原理，还能掌握在实际应用中可能遇到的问题及其解决方案。编辑委员会由来自全球知名高校的专家组成，如Peter Benner、Dianne P. O'Leary、John R. Gilbert和Robert D. Russell等人，他们都是数值分析领域的权威，确保了书籍内容的前沿性和专业性。通过《Direct Methods for Sparse Linear Systems》，读者可以深入了解稀疏矩阵直接求解的理论背景、实施步骤和实际应用，这对于在科研、工程或教学工作中处理稀疏线性问题的人员来说，是一份宝贵的参考资料。

1.1.

Linear

algebra

set of

vectors

, a

, • • •, a

linearly

independent

implies

Q.J

zero

for all j. The

span

of a set of

vectors

is the set of

vectors

that

can be

written

linear combination

vectors

in the

set;

span

a?,...,

)

a^a^}.

The

range

of a

matrix

A is the

span

of its

column vectors.

The

rank

of a

matrix

A is

the

maximal

size

of the

subsets

of the

columns

of A

that

are

linearly independent.

n-by-n matrix

singular

if its

rank

less than

n. An ra-by-n

matrix

rank

deficient

if its

rank

less

than

min(m,

n);

it has

full

rank

otherwise.

The

1-norm

of a

column vector

x or row

vector

||o;||i

\Xi\,

its

2-norm

||a;||2

VTT^F'

its

co-norm

||a;||oo

= max

\Xi\.

The

1-norm

of a

matrix

the

largest 1-norm

of its

column vectors.

The

co-norm

of a

matrix

is the

largest

1-norm

of its row

vectors.

The

inverse

of a

matrix

A is

where

A =

exists

only

A is

square

and

nonsingular.

Two

vectors

x and y are

orthogonal

= 0. A

matrix

Q is

orthonormal

= /. A

real square orthonormal

matrix

called

orthogonal,

which case

= /

(that

is,

if Q is

orthogonal).

The

2-norm

of a

vector

x and the

product

Qx are

identical

if Q is

orthogonal.

The fcth

diagonal

of an ra-by-n

matrix

A is a

vector

consisting

of the set

entries

{a^-},

where

—

i = k. The

term

diagonal,

itself,

refers

to the Oth

diagonal,

main diagonal,

of a

matrix.

The

kih

diagonal entry

of A is

a^fc

•

The

number

nonzero entries

(nonzeros

for

short)

in a

matrix

vector

|-A|,

and

|a|

denotes

the

absolute value

of a

scalar.

permutation matrix

P is a row or

column permutation

of the

identity

matrix.

Any

given

row or

column

of P

contains

single nonzero entry, equal

The

factorization

of a

square nonsingular matrix

A has the

form

LU =

where

L is

lower triangular

and U is

upper triangular. With partial pivoting

and row

interchanges,

the

factorization

is LU = PA. A

matrix

A is

positive

definite

if and

only

> 0 for all

nonzero vectors

x. It is

positive

semidefinite

The

Cholesky

factorization

of a

square symmetric positive

definite

matrix

A has the

form

where

L is

lower triangular with positive diagonal entries. Pivoting

not

required

for

stability.

square matrix

A is

diagonally

dominant

rows

|flti|

^j^i

ij\

f°

an<

*•

strictly

diagonally dominant

rows

(0^)

£),--£i

ij\

f°

*•

(strictly) diagonally dominant

columns

(strictly)

diagonally dominant

rows.

square strictly diagonally dominant matrix

nonsingular. Gaussian elimination without pivoting

form

of LU

factorization)

stable

for any

diagonally dominant matrix

(by

rows

or by

columns).

factorization

of a

rectangular matrix

A is QR =

where

Q is or-

thogonal

and R is

upper triangular.

For a

square matrix

Ax = \x

holds

for an

eigenvalue

A and its

eigenvector

Sets

are

denoted

calligraphic letters

£,

7?.,

X, and y.

These

typically arise

from

the

nonzero

pattern

of the

corresponding matrix

vector.

For

example,

A*j

{i\&ij

0},

and X =

{i\Xi

0}.

The * in the

subscript

dropped

when

the

context

clear.

The

terms

dense

and

sparse

refer

to the

data

structure used

store

matrix.

matrix

mxn

dense

if it is

stored

as a

full

array

of ra

rows

and n

columns

with

ran

entries. This

called

full

matrix

MATLAB.

All

entries

are

stored,

Chapter

Introduction

even

some

them

are

zero.

sparse matrix

stored

in a

data

structure

that

can

exploit sparsity

by not

storing numerically zero entries. Numerically zero entries

may

stored

in a

sparse matrix, typically

as a

result

numerical cancellation.

1.2

Graph

theory,

algorithms,

and

data structures

graph

G =

(V,E)

is a set of

nodes

V =

{!,...,n}

and a set of

edges

E =

{(i,j)

€

connecting those nodes.

In an

undirected

graph,

(i,j]

and

(j,i)

are

the

same edge; they

are

different

edges

in a

directed

graph.

In a

directed graph, there

can be an

edge

(i,j)

but no

edge

(j,i).

The

neighbors

of a

node

i, or

equivalently

the

adjacency

set of i, is

Adj(f)

= {j \

(i,j)

E}.

For a

directed

graph,

this

is the

out-adjacency

node

i. The

in-adjacency

node

i is

InAdj(i)

(j,i)

€

E}.

The

out-adjacency

and

in-adjacency

of a

node

in an

undirected graph

are

identical.

The

adjacency

matrix

A of

graph

G is a

binary

n-by-n

matrix with

= 1 if

(i,j)

€ E, and

= 0

otherwise.

It is

symmetric

if G is

undirected,

and may be

unsymmetric

otherwise.

graph

can

also

represented

as a set of n

adjacency

lists,

Ai*

aij

0} or

A*J

—

aij

0}.

This

relates

the

sparsity

pattern

of an n-

by-n

matrix

A to its

corresponding undirected

directed graph

•

The

diagonal

afcfc

is the

self-edge

(k,

fc); it is

typically excluded

from

GA-

The

degree

of a

node

undirected graph

is the

size

of its

adjacency list,

\A*i\

|A*|

|Adj(«)|.

Two

graphs

are

isomorphic

they

can be

made identical

renumbering their nodes.

node

i is

incident

on the

edge

(a, 6) if a = i or 6 =

the

edge

(a, 6) is

also

said

to be

incident

node

i. A

node-induced

subgraph

G =

(V,

E) of G is

defined

subset

of the

nodes_F

where

{(i,

\(i,j)eE/\i£V/\j£

V}.

edge-induced

subgraph

G =

(V,

E) is

defined

by a set of

edges

E C E,

where

the

nodes

V are all the

nodes incident

on any

edge

in E.

graph

completely connected

if E

V x

it has an

edge between every

pair

nodes.

clique

is a

completely connected subgraph.

path

~»

length

k is a

sequence

nodes

(VQ,

...,

Vk)

where

edge

(vi-i,Vi)

exists between each pair

adjacent nodes

in the

sequence.

The

path

simple

if no

node appears more than once. Node

j is

reachable

from

node

if a

path

exists

in the

graph.

The set of all

nodes reachable

from

i in the

graph

G is

Reached).

graph

strongly

connected

there exists

path

from

any

node

any

other node. That

is,

Reachc?(«)

is the

entire graph

for any

node

i. A

graph

connected

if its

underlying

undirected

graph

strongly

connected.

The

underlying

undirected graph

of G is the

same

as G but

with

all the

edge directions ignored.

cycle

is a

path

~»

where

the first and

last nodes

are the

same.

It is a

simple

cycle

if no

edge

node appears more than once, except

for i

itself.

graph

with

cycles

acyclic.

directed acyclic graph

often

called

DAG,

for

short.

undirected acyclic graph

is a

forest.

tree

is a

connected

forest.

There

is a

unique simple

path

between every pair

nodes

in a

tree.

One

node

of a

rooted

tree

designated

as the

root

The

unique node

following

i in the

path

r is

called

the

parent

p of

the

root itself

has no

parent. Node

i is a

child

node

has at

most

one

parent

but can

have more than

one

child.

node with

children

is a

leaf.

The

path

~»

r is the set of

ancestors

of i.

Node

i is a

descendant

of all

nodes

1.2. Graph

theory,

algorithms,

and

data

structures

the

path

~»

The set of

proper

ancestors

descendants

node

excludes

node

itself.

The

subtree

rooted

node

consists

of the

subgraph induced

by the

nodes

i and its

descendants.

In a

postordered

tree,

the d

proper descendants

of any

node

k are

nodes

—

through

—

bipartite

graph

is an

undirected graph whose nodes

are

partitioned into

two

subsets,

and

every edge connects

two

nodes

different

subsets.

node

separator

subset

S C V of the

nodes

of G =

(V,

such

that

the

graph induced

by the

nodes

V \ S is

unconnected.

edge

separator

is a

subset

S C E of the

edges

G =

(V,E)

such

that

the

graph

G =

(V,E\S)

unconnected.

node

cover

is a

set of

nodes

5 C V

such

that

all

edges

E are

incident

on at

least

one

node

in S.

Informally,

asymptotic notation describes

the

gist

of a

function

f(x):

how

fast

grows

as a

function

of x.

Scalar factors

and

lower

order terms

are

ignored.

For

example,

all

quadratic polynomials

+ bx + 1 are

O(x

unless

formally,

function

/(#)

O(g(x)}

there exist positive constants

c and

such

that

/(#)

cg(x)

for all x

XQ.

This provides

asymptotic upper bound.

The

asymptotic lower bound

defined

similarly.

function

f(x)

£l(g(x})

there

exist positive constants

c and

such

that

cg(x)

f(x)

for all x

XQ.

f(x)

both

O(g(x}}

and

£l(g(x)),

then

it has a

tight asymptotic bound,

Q(g(x}).

Algorithm

analysis

refers

methods

for

determining asymptotic bounds

the run

time, memory usage,

and

other

aspects

of an

algorithm.

The run

time

and

other

statistics

are

typically expressed

functions

of the

size

of the

input.

Worst-case analysis

finds an

upper bound

(O(...))

that

always holds, regardless

the

input.

Average-case

analysis looks

at the

typical case. These

are

often

the

same

but not

always.

The

time complexity

of an

algorithm

is the

asymptotic bound

its run

time.

amortized

analysis

considers

the

total

run

time

of a

sequence

operations.

If the

time

for

operations

T(n),

the

amortized time

for one

operation

T(n)/n.

For

example,

if a

function

called

times

and

takes

one

unit

time

—

times

but n + 1

units

time just once,

the

worst-case time complexity

O(n)

for any one

usage

this

function.

However,

if the

cost

of all n

operations

are

added together

and

amortized across

all

operations,

the

amortized cost

per

operation becomes

just

two, which

O(l).

The

latter

is a

useful

picture

the

time complexity

of one

operation

in a

sequence.

example

where amortized time complexity

useful

is the

dynamic

table

algorithm.

Consider

table

size

that

starts

out

with

k = 1 and an

operation

that

inserts

item

at the end of the

table.

If the

size

k of the

table

insufficient,

it is

doubled

size, taking

O(k)

time

make

the

larger copy. With

insertions,

it may

appear

that

total

time would

O(n

but

this

is not the

case. Even with

this

extra

work

copying

the

table,

the

amortized cost

of a

single insertion

0(1),

because only

the

iih

insertions when

i is a

power

of two

plus

one

require

complete

copy

of the

table.

For n

insertions,

the

time

where

[#J

is the

largest integer

not

greater than

The

total time

for n

insertions

Chapter

Introduction

less than

equal

3n.

The

amortized time

for any one

insertion

is at

most

common class

graph algorithms consists

methods

for

traversing

the

nodes

and

edges

of a

graph.

The

depth-first

of a

graph

starts

at a

node

j and

finds

all

nodes reachable

from

node

.;'.

explores recursively

always examining

the

outgoing edges

of the

latest

node

just seen. When

all

edges

of i

have been

explored,

backtracks

to the

node

from

which

i was first

discovered. Nodes

are

marked

that

they

are not

searched twice.

The

time taken

by a

depth-first search

O(s + e),

where

s =

|Reach(i)|

and e is the

number

edges

in the

subgraph

induced

by s.

This subgraph

connected

by the way it is

constructed. Traversing

the

entire graph

in a

depth-first manner requires

the

traversal

to be

repeated until

all

nodes

are

visited.

depth-first search produces

list

nodes

of a DAG in

topological

order,

appears

before

j if i

j is a

path

in G.

The

breadth-first

traverses

graph

in a

different

order. Starting

node

i, it first

examines

all

nodes adjacent

to i.

Next,

examines

all

nodes

whose

shortest path

j is of

length

then length

3, and so on.

the

depth-first

search,

it too

traverses

all

nodes

Reach^).

Unlike

the

depth-first search,

traverses these nodes

order

of the

shortest

path

from

i, not in

topological order.

graph

denoted

as G or

and T

denotes

tree

forest.

denotes

the

element lists

in the

minimum

degree ordering algorithm, discussed

Chapter

1.3

Further

reading

Golub

and Van

Loan

[114]

provide

in-depth

coverage

numerical linear

algebra

and

matrix computations

for

dense

and

structured matrices; Strang [193] gives

introduction

linear algebra.

Moler

[157] provides

introduction

numerical

computing

with

strong MATLAB

focus.

Stewart presents

in-depth look

matrix decompositions [190]

and

eigenvalue problems

[191].

Higham

[135] discusses

the

behavior

numerical algorithms

in finite

precision arithmetic.

Gormen,

Leiserson,

and

Rivest [23] discuss algorithms

and

data

structures

and

their analysis, including graph algorithms. Kernighan

and

Ritchie [141]

give

concise coverage

of the C

programming language. Higham

and

Higham [133],

Davis

and

Sigmon [38],

or the

online documentation

for

MATLAB

are

good places

learn more about

MATLAB.

The

books

Duff,

Erisman,

and

Reid [53]

and

George

and Liu

[89] both deal

with

direct methods

for

sparse matrices;

the

latter

focuses

symmetric positive

definite

matrices. Gilbert [101]

and Liu

[150] provide

overview

much

of the

graph

theory related

sparse direct methods. Stewart [192] provides

tutorial-

level

description

sparse

Cholesky. Gould,

Hu, and

Scott

[116]

survey

wide

range

software

packages

for the

factorization

sparse symmetric matrices. Iterative

methods

for

sparse linear systems

and the

incomplete factorization methods they

rely

on are

discussed

Saad

[178],

Greenbaum

[117],

and

Barrett

al.

[15].

Bjorck

[17]

presents direct

and

iterative methods

for

sparse least squares problems.

Parlett

[164]

provides

in-depth

look

at the

symmetric eigenvalue problem

for

sparse

matrices.

Demmel

[39] interleaves

discussion

numerical linear algebra with

description

software

for

sparse

and

dense problems.

剩余229页未读，继续阅读

lyricx

粉丝: 0
资源: 2

稀疏线性系统直接求解方法——Timothy A Davis

Iterative methods for sparse linear systems (1st edition)

Direct_Methods_for_Sparse_Linear_Systems

Iterative Methods for Sparse Linear Systems

Iterative Methods for Sparse Linear Systems_Fortran_稀疏_声学编程文件_

yousef saad iterative methods for sparse linear systems

Iterative Methods for sparse linear space.pdf

Direct methods for sparse matrices

Direct Methods for Sparse Matrices (I. S. Duff, A. M. Erisman, J. K. Reid)

sparse direct methods for linear systems

sparse linear systems

最新资源