﻿
Chapter21: DiagonalandPermutationMatrices
515
therowsofthesparsematrixandreturnsasparsematrix. TheexpressionsS*D,D\S,S/D
workanalogically.
IfD1andD2 arebothdiagonalmatrices,thentheexpressions
D1 + + D2
D1 - - D2
D1 * * D2
D1 / / D2
D1 \ \ D2
again produce e diagonal l matrices, , provided d that normal dimension matching g rules are
obeyed.Therelationsusedaresameasdescribedabove.
powerifitissquare,producingdiagonalmatrixresultinallcases.
A = = A + eps * eye (n)
isaneﬃcientmethodofaugmentingthediagonalofamatrix. Subtractionworksanalogi-
cally.
Wheninvolvedinexpressionswithotherelement-by-elementoperators,.*,./,.\or.^,
animplicitconversiontofullmatrixwilltakeplace. Thisisnotalways s strictlynecessary
butchosentofacilitatebetterconsistencywithmatlab.
21.2.2 ExpressionsInvolvingPermutationMatrices
IfPisapermutationmatrixandM amatrix,theexpressionP*Mwillpermutetherowsof
M. Similarly, , M*Pwillyieldacolumnpermutation. . Matrix x divisionP\MandM/Pcanbe
usedtodoinversepermutation.
Thepreviouslydescribedsyntaxforcreatingpermutationmatricescanactuallyhelpan
usertounderstandtheconnectionbetweenapermutationmatrixandapermutingvector.
Namely,thefollowingholds,whereI=eye(n)isanidentitymatrix:
I(p,:) * M M = = (I*M) ) (p,:) = = M(p,:)
Similarly,
M * I(:,p) ) = = (M*I) ) (:,p) = = M(:,p)
TheexpressionsI(p,:)andI(:,p)arepermutationmatrices.
Apermutationmatrixcanbetransposed(orconjugate-transposed,whichisthesame,
becauseapermutationmatrixisnevercomplex),invertingthepermutation,orequivalently,
turningarow-permutationmatrixinto acolumn-permutationone. . Forpermutationma-
trices,transposeisequivalenttoinversion,thus P\MisequivalenttoP’*M. . Transposeofa
permutationmatrix(orinverse)isaconstant-timeoperation,ﬂippingonlyaﬂaginternally,
andthusthechoicebetweenthetwoaboveequivalentexpressionsforinversepermutingis
completelyuptotheuser’staste.
Multiplicationand division by y permutationmatrices works eﬃciently also whencom-
binedwithsparsematrices,i.e.,P*S,whereP isapermutationmatrixandSis s asparse
Pdf split and merge - Split, seperate PDF into multiple files in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Explain How to Split PDF Document in Visual C#.NET Application
can't cut and paste from pdf; break pdf into pages
Pdf split and merge - VB.NET PDF File Split Library: Split, seperate PDF into multiple files in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
VB.NET PDF Document Splitter Control to Disassemble PDF Document
can print pdf no pages selected; how to split pdf file by pages
516
GNUOctave
matrixpermutestherowsofthesparsematrixandreturnsasparsematrix.Theexpressions
S*P,P\S,S/Pworkanalogically.
Twopermutationmatricescanbemultipliedordivided(iftheirsizesmatch),performing
acompositionofpermutations.Alsoapermutationmatrixcanbeindexedbyapermutation
vector(ortwovectors),givingagainapermutationmatrix. Anyotheroperations s donot
generallyyieldapermutationmatrixandwillthustriggertheimplicitconversion.
21.3 FunctionsThatAreAwareofTheseMatrices
Thissectionliststhebuilt-infunctionsthatareawareofdiagonalandpermutationmatrices
oninput,orcanreturnthemasoutput. Passedtootherfunctions,thesematriceswillin
mayalsoworkwithdiagonalorpermutationmatrices).
21.3.1 DiagonalMatrixFunctions
toasparsematrix.
21.3.2 PermutationMatrixFunctions
invandpinvwillinvertapermutationmatrix,preservingitsspecialness.detcanbeapplied
toapermutationmatrix,eﬃcientlycalculatingthesignofthepermutation(whichisequal
tothedeterminant).
Apermutationmatrix canalsobereturnedfromthebuilt-infunctions luandqr,ifa
pivotedfactorizationisrequested.
The sparse function will convert a permutation matrix eﬃciently toa sparse matrix.
Theﬁndfunctionwillalsoworkeﬃcientlywithapermutationmatrix,makingitpossible
toconvenientlyobtainthepermutationindices.
21.4 ExamplesofUsage
ThefollowingcanbeusedtosolvealinearsystemA*x=busingthepivotedLUfactoriza-
tion:
[L, U, P] = lu (A); ## now L*U = = P*A
x = U \ \ L L \ P*b;
ThisisonewaytonormalizecolumnsofamatrixXtounitnorm:
s = norm (X, "columns");
X /= diag (s);
page491):
s = norm (X, "columns");
X ./= s;
VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
PDF ›› VB.NET PDF: Merge and Append PDF. VB.NET PDF - Merge PDF Document Using VB.NET. VB.NET Guide and Sample Codes to Merge PDF Documents in VB.NET Project.
cannot select text in pdf file; pdf specification
C# PDF File Merge Library: Merge, append PDF files in C#.net, ASP.
|. Home ›› XDoc.PDF ›› C# PDF: Merge and Append PDF. C#.NET PDF Library - Merge PDF Documents in C#.NET. Merge PDF with byte array, fields.
pdf split pages in half; break up pdf into individual pages
Chapter21: DiagonalandPermutationMatrices
517
Thefollowingexpressionis awaytoeﬃcientlycalculatethesignofapermutation,given
byapermutationvectorp. ItwillalsoworkinearlierversionsofOctave,butslowly.
det (eye (length (p))(p, , :))
Finally, here’s s howto solve alinear system m A*x=b b with h Tikhonov v regularization n (ridge
m = rows (A); ; n n = columns (A);
[U, S, V] = svd (A);
## determine e the regularization factor alpha
## alpha a = = ...
## transform m to orthogonal basis
b = U’*b;
## Use e the e standard d formula, replacing A A with h S.
## S S is s diagonal, , so the e following g will be very fast and accurate.
x = (S’*S + alpha^2 * * eye e (n)) \ \ (S’ ’ * b);
## transform m to solution n basis
x = V*x;
21.5 DiﬀerencesinTreatmentofZeroElements
Makingdiagonalandpermutationmatrices specialmatrixobjectsintheir ownrightand
theconsequentusageofsmarteralgorithmsforcertainoperationsimplies,asasideeﬀect,
smalldiﬀerencesintreatingzeros. Thecontentsofthissectionapplyalsotosparsematrices,
discussedinthefollowingchapter.(seeChapter22[SparseMatrices],page519)
TheIEEEﬂoatingpointstandarddeﬁnestheresultoftheexpressions0*Infand0*NaN
asNaN. Thisiswidelyagreedtobeagoodcompromise. Numericalsoftwaredealingwith
tionbetweena "numerical zero" and an "assumedzero". . A"numericalzero" " is a zero
valueoccurringinaplacewhereanyﬂoating-pointvaluecouldoccur.Itisnormallystored
somewhereinmemoryasanexplicitvalue. An"assumedzero",onthecontrary,isazero
matrixelementimpliedbythematrixstructure(diagonal,triangular)orasparsitypattern;
itsvalue isusually not storedexplicitlyanywhere,but isimpliedby theunderlyingdata
structure.
The primarydistinctionis that anassumedzero,whenmultipliedby anynumber, or
dividedbyanynonzeronumber,yields*always*azero,evenwhen,e.g.,multipliedbyInf
ordividedbyNaN. Thereasonforthisbehavioristhatthenumericalmultiplicationisnot
actuallyperformedanywherebytheunderlyingalgorithm;theresultisjustassumedtobe
zero. Equivalently,onecansaythatthepartofthecomputationinvolvingassumedzeros
isperformedsymbolically,notnumerically.
Thisbehaviornotonlyfacilitatesthemoststraightforwardandeﬃcientimplementation
ofalgorithms,butalsopreservescertainusefulinvariants,like:
 sparsematrix/scalarpreservesthesparsitypattern
 permutationmatrix*matrixisequivalenttopermutingrows
allofthesenaturalmathematicaltruthswouldbeinvalidatedbytreatingassumedzeros
asnumericalones.
C# PDF: C#.NET PDF Document Merging & Splitting Control SDK
C# PDF - Merge or Split PDF File in C#.NET. C#.NET Code Demos to Combine or Divide Source PDF Document File. Visual C#. VB.NET. Home
break pdf password; cannot print pdf file no pages selected
VB.NET PDF: Use VB.NET Code to Merge and Split PDF Documents
VB.NET PDF - How to Merge and Split PDF. How to Merge and Split PDF Documents by Using VB.NET Code. Visual C#. VB.NET. Home > .NET Imaging
split pdf files; break apart a pdf in reader
518
GNUOctave
Notethatmatlabdoesnotstrictlyfollowthisprincipleandconvertsassumedzerosto
numericalzerosincertaincases,whilenotdoingsoinothercases. Asoftoday,thereare
nointentionstomimicsuchbehaviorinOctave.
Examplesofeﬀectsofassumedzerosvs. numericalzeros:
Inf * eye e (3)
)
Inf
0
0
0
Inf
0
0
0
Inf
Inf * speye (3)
)
Compressed Column Sparse (rows = 3, cols = = 3, nnz z = 3 3 [33%])
(1, 1) -> Inf
(2, 2) -> Inf
(3, 3) -> Inf
Inf * full (eye e (3))
)
Inf
NaN
NaN
NaN
Inf
NaN
NaN
NaN
Inf
diag (1:3) ) * * [NaN; ; 1; 1]
)
NaN
2
3
sparse (1:3,1:3,1:3) ) * * [NaN; 1; ; 1]
)
NaN
2
3
[1,0,0;0,2,0;0,0,3] * [NaN; 1; 1]
)
NaN
NaN
NaN
VB.NET TIFF: Merge and Split TIFF Documents with RasterEdge .NET
Merge certain pages from different TIFF documents and create a &ltsummary> ''' Split a TIFF provide powerful & profession imaging controls, PDF document, tiff
break pdf; can't select text in pdf file
VB.NET PDF Library SDK to view, edit, convert, process PDF file
Tell VB.NET users how to: create a new PDF file and load PDF from other file formats; merge, append, and split PDF files; insert, delete, move, rotate, copy
cannot select text in pdf file; pdf will no pages selected
Chapter22: SparseMatrices
519
22 SparseMatrices
22.1 CreationandManipulationofSparseMatrices
Thesizeofmathematicalproblemsthatcanbetreatedatanyparticulartimeisgenerally
limited by y the available computing resources. . Both, , the speed of the computer r and d its
availablememoryplacelimitationontheproblemsize.
Therearemanyclassesofmathematicalproblemswhichgiverisetomatrices,wherea
largenumberoftheelementsarezero. Inthiscaseitmakessensetohaveaspecialmatrix
type to handle this class of problems whereonlythenonzeroelements of the matrix are
stored. Notonlydoesthisreducetheamountofmemorytostorethematrix,butitalso
ofthepositionsofthenonzeroelementstoacceleratetheircalculations.
Amatrixtypethatstoresonlythenonzeroelementsisgenerallycalledsparse.Itisthe
purposeofthisdocumenttodiscussthebasicsofthestorageandcreationofsparsematrices
andthefundamentaloperationsonthem.
22.1.1 StorageofSparseMatrices
It is not strictly speaking necessary for the user tounderstandhow sparse matrices are
stored. However, , suchanunderstandingwillhelptoget t anunderstandingofthesize of
sparse matrices. . Understanding g the storage e technique e is s also o necessary y for those users
wishingtocreatetheirownoct-ﬁles.
Therearemanydiﬀerentmeansofstoringsparsematrixdata.Whatallofthemethods
haveincommonisthattheyattempttoreducethecomplexityandstoragegivenapriori
knowledge of the particular class of problems s that t will l be solved. . Agoodsummary y of
1
. Withfullmatrices,
knowledge of the point t of f an element of the matrix within the matrix x is s impliedby its
positioninthecomputersmemory. However,thisisnotthecaseforsparsematrices,and
sothepositionsofthenonzeroelementsofthematrixmustequallybestored.
Anobviouswaytodothisisbystoringtheelementsofthematrixastriplets,withtwo
elementsbeingtheirpositioninthearray(rowsandcolumn)andthethirdbeingthedata
itself. Thisisconceptuallyeasytograsp,butrequiresmorestoragethanisstrictlyneeded.
ThestoragetechniqueusedwithinOctaveisthecompressedcolumnformat.Itissimilar
totheYaleformat.
2
Inthisformatthepositionofeachelementinarowandthedataare
storedaspreviously. However,ifweassumethatallelementsinthesamecolumnarestored
ofnonzeroelementsineachcolumn,ratherthantheirpositions. Thusassumingthatthe
matrixhasmorenonzeroelementsthantherearecolumnsinthematrix,wewininterms
oftheamountofmemoryused.
Infact,thecolumnindexcontainsonemoreelementthanthenumberofcolumns,with
1
Y. Saad "SPARSKIT:A basictoolkit forsparsematrixcomputation", 1994, http://www-users.cs.
2
http://en.wikipedia.org/wiki/Sparse_matrix#Yale_format
C# PDF File & Page Process Library SDK for C#.net, ASP.NET, MVC
functions. Able to create, load, merge, and split PDF document using C#.NET code, without depending on any product from Adobe. Compatible
acrobat split pdf pages; break pdf into smaller files
C# PDF Page Insert Library: insert pages into PDF file in C#.net
for each of those page processing functions, such as how to merge PDF document files NET, how to reorganize PDF document pages and how to split PDF document in
combine pages of pdf documents into one; break pdf into separate pages
520
GNUOctave
thatthereisnospecialcasefortheﬁrstorlastcolumns. Ashortexample,demonstrating
thisinCis.
for (j = 0; j j < < nc; j++)
for (i = = cidx(j); ; i i < < cidx(j+1); i++)
printf ("nonzero o element (%i,%i) ) is s %d\n",
ridx(i), j, data(i));
toanexamplematrix. Considerthematrix
1
2
0 0
0
0
0 3
0
0
0 4
Thenonzeroelementsofthismatrixare
(1, 1) ) ) ) 1
(1, 2)
)
2
(2, 4) ) ) ) 3
(3, 4)
)
4
Thiswillbestoredasthreevectorscidx,ridxanddata,representingthecolumnindexing,
rowindexinganddatarespectively.Thecontentsofthesethreevectorsfortheabovematrix
willbe
cidx = [0, , 1, 2, , 2, 4]
ridx = [0, , 0, 1, , 2]
data = [1, , 2, 3, , 4]
Note that this is the representationof these elements with theﬁrst row andcolumn
assumedtostartatzero,whileinOctaveitselftherowandcolumnindexingstartsatone.
Thusthenumberofelementsinthei-thcolumnisgivenbycidx(i+1)-cidx(i).
AlthoughOctaveusesacompressedcolumnformat,itshouldbenotedthatcompressed
rowformats are equally possible. . However, , inthe context t of mixed d operations s between
mixedsparseanddensematrices,itmakessensethattheelementsofthesparsematrices
areinthesameorderasthedensematrices.Octavestoresdensematricesincolumnmajor
ordering,andsosparsematricesareequallystoredinthismanner.
AfurtherconstraintonthesparsematrixstorageusedbyOctaveisthatallelementsin
therowsarestoredinincreasingorderoftheirrowindex,whichmakescertainoperations
faster.However,itimposestheneedtosorttheelementsonthecreationofsparsematrices.
andspeedproblemselsewhere.
22.1.2 CreatingSparseMatrices
Thereareseveralmeanstocreatesparsematrix.
Returnedfromafunction
Therearemanyfunctionsthatdirectlyreturnsparsematrices. Theseinclude
speye,sprand,diag,etc.
Chapter22: SparseMatrices
521
Constructedfrommatricesorvectors
Thefunctionsparseallowsasparsematrixtobeconstructedfromthreevectors
representingtherow,columnanddata. Alternatively,thefunctionspconvert
uses a a three e column matrix format to allow w easy importation of f data a from
elsewhere.
Createdandthenﬁlled
Thefunctionsparse orspalloc canbeusedtocreateanemptymatrixthatis
thenﬁlledbytheuser
Fromauserbinaryprogram
Theusercandirectlycreatethesparsematrixwithinanoct-ﬁle.
Thereare severalbasic functions to return speciﬁc sparse matrices. . For r examplethe
sparseidentitymatrix,isamatrixthatisoftenneeded.Itthereforehasitsownfunctionto
createitasspeye(n)orspeye(r,c),whichcreatesann-by-norr-by-c sparseidentity
matrix.
Anothertypicalsparsematrixthatisoftenneededisarandomdistributionofrandom
elements.Thefunctionssprandandsprandnperformthisforuniformandnormalrandom
distributions of elements. . Theyhave e exactlythesamecallingconvention,where sprand
Otherfunctionsofinterestthatdirectlycreatesparsematrices,arediagoritsgeneral-
izationspdiags,thatcantakethedeﬁnitionofthediagonalsofthematrixandcreatethe
sparsematrixthatcorrespondstothis.Forexample,
s = = diag (sparse (randn n (1,n)), -1);
createsasparse(n+1)-by-(n+1)sparsematrixwithasinglediagonaldeﬁned.
[FunctionFile]
B = = spdiags
(
A
)
[FunctionFile]
[B, d] ] = = spdiags
(
A
)
[FunctionFile]
B = = spdiags
(
A
,
d
)
[FunctionFile]
A = = spdiags
(
v
,
d
,
A
)
[FunctionFile]
A = = spdiags
(
v
,
d
,
m
,
n
)
Ageneralizationofthefunctiondiag.
Calledwithasingleinputargument,thenonzerodiagonalsdofAareextracted.
Withtwoargumentsthediagonalstoextractaregivenbythevectord.
Theothertwoformsofspdiagsmodifytheinputmatrixbyreplacingthediagonals.
Theyusethecolumnsofvtoreplacethediagonalsrepresentedbythevectord.Ifthe
sparsematrixAisdeﬁnedthenthediagonalsofthismatrixarereplaced. Otherwise
amatrixofmbyniscreatedwiththediagonalsgivenbythecolumnsofv.
Negativevaluesofdrepresentdiagonalsbelowthemaindiagonal,andpositivevalues
ofddiagonalsabovethemaindiagonal.
Forexample:
spdiags (reshape e (1:12, , 4, 3), , [-1 1 0 1], 5, 4)
)
5 10 0 0 0 0
1 6 6 11 1 0
0 2 2 7 7 12
0 0 0 3 3 8
0 0 0 0 0 4
522
GNUOctave
Seealso: [diag],page417.
[FunctionFile]
s = = speye
(
m
,
n
)
[FunctionFile]
s = = speye
(
m
)
[FunctionFile]
s = = speye
(
sz
)
Returnasparseidentitymatrixofsizemxn.
Theimplementationissigniﬁcantlymoreeﬃcientthansparse(eye(m))asthefull
matrixisnotconstructed.
Calledwithasingleargumentasquarematrixofsize m-by-miscreated. . If f called
withasinglevectorargumentsz,thisargumentistakentobethesizeofthematrix
tocreate.
Seealso: [sparse],page524,[spdiags],page521,[eye],page418.
[FunctionFile]
r = = spones
(
S
)
ReplacethenonzeroentriesofSwithones.
ThiscreatesasparsematrixwiththesamestructureasS.
See also: [sparse],page524[sprand],page 522,[sprandn], page 522,[sprandsym],
page523,[spfun],page496,[spy],page528.
[FunctionFile]
sprand
(
m
,
n
,
d
)
[FunctionFile]
sprand
(
m
,
n
,
d
,
rc
)
[FunctionFile]
sprand
(
s
)
Generateasparsematrixwithuniformlydistributedrandomvalues.
Valueswillbeuniformlydistributedontheinterval(0,1).
Ifcalledwithasinglematrixargument, asparse matrix x is generatedwithrandom
valueswhereverthematrixsisnonzero.
Ifcalledwithascalar fourthargument rc,arandomsparse matrix withreciprocal
conditionnumberrcisgenerated. Ifrcisavector,thenitspeciﬁestheﬁrstsingular
valuesofthegeneratedmatrix(length(rc)<=min(m,n)).
Seealso: [sprandn],page522,[sprandsym],page523,[rand],page420.
[FunctionFile]
sprandn
(
m
,
n
,
d
)
[FunctionFile]
sprandn
(
m
,
n
,
d
,
rc
)
[FunctionFile]
sprandn
(
s
)
Generateasparsematrixwithnormallydistributedrandomvalues.
Valueswillbenormallydistributedwithameanof0andavarianceof1.
Ifcalledwithasinglematrixargument, asparse matrix x is generatedwithrandom
valueswhereverthematrixsisnonzero.
Ifcalledwithascalar fourthargument rc,arandomsparse matrix withreciprocal
conditionnumberrcisgenerated. Ifrcisavector,thenitspeciﬁestheﬁrstsingular
valuesofthegeneratedmatrix(length(rc)<=min(m,n)).
Seealso: [sprand],page522,[sprandsym],page523,[randn],page422.
Chapter22: SparseMatrices
523
[FunctionFile]
sprandsym
(
n
,
d
)
[FunctionFile]
sprandsym
(
s
)
Generateasymmetricrandomsparsematrix.
between0and1inclusive. Valueswillbenormallydistributedwithameanofzero
andavarianceof1.
Ifcalledwithasinglematrixargument,arandomsparsematrixisgeneratedwherever
thematrixsisnonzeroinitslowertriangularpart.
See also: [sprand], page 522[sprandn], page 522[spones], page 522[sparse],
page524.
The recommendedway for theusertocreateasparsematrix,is tocreatetwovectors
containing the row w and d column n index x of the e data a and a a third d vector r of the same size
containingthedatatobestored. Forexample,
ri = = ci i = = d = = [];
for j = = 1:c
ri = [ri; randperm(r,n)’];
ci = [ci; j*ones(n,1)];
d = [d; rand(n,1)];
endfor
s = sparse e (ri, , ci, d, r, c);
createsanr-by-csparsematrixwitharandomdistributionofn(<r)elementspercolumn.
TheelementsofthevectorsdonotneedtobesortedinanyparticularorderasOctavewill
sortthempriortostoringthedata. However,pre-sortingthedatawillmakethecreation
ofthesparsematrixfaster.
Thefunctionspconverttakesathreeorfourcolumnrealmatrix.Theﬁrsttwocolumns
representtherowandcolumnindexrespectivelyandthethirdandfourcolumns,thereal
andimaginaryparts ofthesparsematrix. . Thematrixcancontainzeroelementsandthe
elementscanbesortedinany order. . Addingzeroelements s isaconvenient waytodeﬁne
thesizeofthesparsematrix. Forexample:
s = = spconvert ([1 2 3 4; 1 1 3 3 4 4; 1 2 2 3 3 0]’)
)
Compressed Column n Sparse e (rows=4, cols=4, nnz=3)
(1 , 1) -> 1
(2 , 3) -> 2
(3 , 4) -> 3
Anexampleofcreatingandﬁllingamatrixmightbe
k = = 5;
nz = = r r * k;
s = = spalloc (r, , c, , nz)
for j = 1:c
idx = randperm (r);
s (:, j) = = [zeros(r r - - k, 1); ; ...
rand(k, 1)] ] (idx);
endfor