Chemistry Reference
In-Depth Information
TABLE 8.2
Storage Requirements (in Millions of Bytes) for a Single Matrix Associated
with the TB Computation of a Gold Cluster with the Speciied Number
of Atoms
Memory
for Sparse
Storage
Memory
for Dense
Storage
Ratio
(Dense/
Sparse)
Number
of Atoms
Matrix
Dimension
Number of
Non-Zeros
Density
(%)
13
117
8,041
58.7
0.1
0.1
1.1
55
495
74,375
30.4
0.9
1.9
2.2
147
1,323
263,011
15.0
3.0
13.4
4.4
309
2,781
638,169
8.3
7.3
59.0
8.1
561
5,049
1,264,069
5.0
14.5
194.5
13.4
923
8,307
2,201,763
3.2
25.2
526.5
20.9
1,415
12,735
3,519,215
2.2
40.3
1,237.3
30.7
2,057
18,513
5,274,949
1.5
60.4
2,614.8
43.3
2,869
25,821
7,529,793
1.1
86.3
5,086.7
59.0
3,871
34,839
10,354,207
0.9
118.6
9,260.2
78.1
5,083
45,747
13,802,299
0.7
158.1
15,966.7
101.0
In.order.to.study.systems.containing.thousands.of.atoms,.sparse.matrix.storage.
techniques. may. be. employed.. The. idea. of. sparse. storage. is. to. store. only. matrix.
elements. that. are. non-zero.. For. matrices. with. many. zero. elements,. this. scheme.
can. be. quite. eficient.. However,. there. is. an. overhead. associated. with. the. point-
ers. needed. to. keep. track. of. the. indices. of. the. matrix. elements.. There. are. many.
schemes. for. sparse. matrix. storage.. One. popular. matrix. scheme. is. CSR. (com-
pressed.sparse.row)..In.this.scheme,.an.index.indicating.the.start.of.each.row.is.
kept.as.well.as.an.index.indicating.the.column.of.each.matrix.element..Thus,.the.
storage. requirement. is. proportional. to. the. matrix. dimension. plus. the. number. of.
non-zero.elements.in.the.matrix..For.a.nice.overview.of.sparse.matrix.storage.and.
related. techniques,. see. Davis. [100].. In. Table. 8.2,. the. sparse. storage,. including.
overhead,.for.a.series.of.gold.clusters.is.given..Note.that.by.the.time.the.cluster.
size. reaches. 5000. atoms,. the. sparse. storage. scheme. is. two. orders. of. magnitude.
more.eficient.than.the.dense.(
n
2
).storage.scheme..These.results.are.taken.from.our.
EHTB.code.that.uses.a.cutoff.distance.(12.
a
0
.in.this.case).beyond.which.matrix.
elements.are.taken.to.be.zero.
There.are.some.drawbacks.to.using.sparse.matrix.techniques..Though.there.are.
a.number.of.libraries.available.that.implement.linear.algebra.operations.on.sparse.
matrices,. these. have. not. seen. widespread. adoption. for. reasons. that. are. not. clear..
Another.reason.for.the.lesser.popularity.of.sparse.matrix.schemes.is.the.relatively.
poor.performance.versus.optimized.math.libraries.such.as.the.BLAS..The.primary.
cause.of.the.poor.performance. is.poor.data.locality.and.irregular.data.access.pat-
terns..Nevertheless,.for.a.matrix.of.suficiently.large.dimension.(perhaps.a.few.thou-
sand),.the.performance.of.linear.algebra.operations.on.sparse.matrices.exceeds.that.
Search WWH ::
Custom Search