Other Languages - data structur - Asked By Hafiz Ullah on 23-Nov-11 10:11 AM

detail definition
Q :-sparse metrics.
Suchit shah replied to Hafiz Ullah on 23-Nov-11 10:56 AM
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . 
Conceptually, sparsity corresponds to systems which are loosely coupled. Consider a line of balls connected by springs from one to the next; this is a sparse system. By contrast, if the same line of balls had springs connecting each ball to all other balls, the system would be represented by a dense matrix. The concept of sparsity is useful in combinatorics and application areas such as network theory, which have a low density of significant data or connections.
Huge sparse matrices often appear in science or engineering when solving partial differential equations.
When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Operations using standard dense matrix structures and algorithms are slow and consume large amounts of memory when applied to large sparse matrices. Sparse data is by nature easily compressed, and this compression almost always results in significantly less computer data storage usage. Indeed, some very large sparse matrices are infeasible to manipulate with the standard dense algorithms.

The native data structure for a matrix is a two-dimensional array. Each entry in the array represents an element ai,j of the matrix and can be accessed by the two indices i and j. For an m×n matrix, enough memory to store at least (m×n) entries to represent the matrix is needed.
Substantial memory requirement reductions can be realized by storing only the non-zero entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to a native approach.
Formats can be divided into two groups: (1) those that support efficient modification, and (2) those that support efficient matrix operations. The efficient modification group includes DOK, LIL, and COO and is typically used to construct the matrix. Once the matrix is constructed, it is typically converted to a format, such as CSR or CSC, which is more efficient for matrix operations.

A sparse matrix is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse n×n matrix with cn entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factorize (with high probability and for large enough c; Gilbert et al. 1992).

If a matrix A is stored in ordinary (dense) format, then the command S = sparse(A) creates a copy of the matrix stored in sparse format. For example:

>> A = [0 0 1;1 0 2;0 -3 0]
A =
     0     0     1
     1     0     2
     0    -3     0
>> S = sparse(A)
S =
   (2,1)        1
   (3,2)       -3
   (1,3)        1
   (2,3)        2
>> whos
  Name      Size         Bytes  Class

  A         3x3             72  double array
  S         3x3             64  sparse array

Grand total is 13 elements using 136 bytes

Unfortunately, this form of the sparse command is not particularly useful, since if A is large, it can be very time-consuming to first create it in dense format. The command S = sparse(m,n) creates antex2html_wrap_inline707 zero matrix in sparse format. Entries can then be added one-by-one:


Neha Garg replied to Hafiz Ullah on 23-Nov-11 01:11 PM
Hello Hafiz,

A good operational definition is that a matrix is sparse if it contains enough zero entries to be worth taking advantage of them to reduce both the storage and work required in solving a linear system. Ideally, we would like to store and operate on only the nonzero entries of the matrix, but such a policy is not necessarily a clear win in either storage or work. The difficulty is that sparse data structures include more overhead (to store indices as well as numerical values of nonzero matrix entries) than the simple arrays used for dense matrices, and arithmetic operations on the data stored in them usually cannot be performed as rapidly either (due to indirect addressing of operands). There is therefore a tradeoff in memory requirements between sparse and dense representations and a tradeoff in performance between the algorithms that use them.

Description

sparse is used to build a sparse matrix. Only non-zero entries are stored.

sp = sparse(X) converts a full matrix to sparse form by squeezing out any zero elements. (If X is already sparse sp is X).

sp=sparse(ij,v [,mn]) builds an mn(1)-by-mn(2) sparse matrix with sp(ij(k,1),ij(k,2))=v(k). ij and v must have the same column dimension. If optional mn parameter is not given the sp matrix dimensions are the max value of ij(:,1) and ij(:,2) respectively.

Operations (concatenation, addition, etc,) with sparse matrices are made using the same syntax as for full matrices.

Elementary functions are also available (abs,maxi,sum,diag,...) for sparse matrices.

Mixed operations (full-sparse) are allowed. Results are full or sparse depending on the operations.

Examples

sp=sparse([1,2;4,5;3,10],[1,2,3])
size(sp)
x=rand(2,2);abs(x)-full(abs(sparse(x)))
Devil Scorpio replied to Hafiz Ullah on 23-Nov-11 03:46 PM
Hi,

Sparse Matrix
    
A sparse matrix is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse n×n matrix with cn entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factorize (with high probability and for large enough)

Sparse Matrix - Example

A selection of articles related to Sparse Matrix - Example:

A computer printer is a computer peripheral device that produces a hard copy (permanent human-readable text and/or graphics, usually on paper) from data stored in a computer connected to it. The world's first computer printer was a 19th-century mechanically driven apparatus invented by Charles Babbage for his Difference Engine. Computer printer - Printing mode

The naive data structure for a matrix is a two dimensional array. Each entry in the array represents an element ai,j of the matrix and can be accessed by the two indices i and j. For a n×m matrix we need at least (n*m) / 8 bytes to represent the matrix when assuming 1 bit for each entry
Jitendra Faye replied to Hafiz Ullah on 23-Nov-11 11:03 PM
Follow this example , here you will get create, read, update example in XML file.


Creating a XML document
To create a XML document
 

using

System.Xml.Linq;
..

#region

CreateCustomerXMLfile

public

static void CreateCustomerXMLfile(string filename)
{
  XElement connections = 
  new XElement("Customers"
  new XElement("Customer",
  n
ew XElement("Id", "0")
  new XElement("Name", "default")));
  connections.Save(filename);
}

#endregion


To call the function and create the XML file in c:\temp\customer.xml

CreateCustomerXMLfile("c:\\temp\\customer.xml");
 

 
Add a record to the Customer XML document
To add a record to the customer xml document we create the following function
 

#region

AddCustomerToXMLfile
public static string AddCustomerToXMLfile(string XMLfile, string Id, string Name)
{
  XDocument XMLDoc = XDocument.Load(XMLfile);
  XElement root = XMLDoc.Root;
  root.Add(
new XElement("Customer",
  new XElement("Id", Id),
  new XElement("Name", Name)));
  XMLDoc.Save(XMLfile);
  return Id;
}
#endregion
 
Call the function a new record will be created with id 1 name Mark

AddCustomerToXMLfile("c:\\temp\\Customer.xml","1","Mark");

 
Update a record in a XML document
 
First we create a customer class
 

#region

Customer Class
public class Customer
{
public string ID;
public string NAME;
}
#endregion
 
Next we create the function to update the specific record we will call this function UpdateCustomerInXMLfile.
The function wil try to find the Id in the XML document and update it with the Name parameter.
 

#region UpdateCustomerInXMLfile
string
UpdateCustomerInXMLfile(string XMLfile, string Id, string Name)
{
Customer customer = new Customer();
XDocument XMLDoc = XDocument.Load(XMLfile);

IEnumerable<XElement> elem_list = from elem in XMLDoc.Descendants("Customer")
                           where elem.Element("Id").Value == customer.ID
                           select elem;

XElement[] elem_array = elem_list.ToArray();
foreach (XElement elem in elem_array)
{
  elem.Element("Id").Value = customer.ID.ToString(); 
  elem.Element(
"Name").Value = customer.NAME.ToString();
}
return Id;
}

#endregion

 
Now we are ready to call the update function

UpdateCustomerInXMLfile(

"c:\\temp\\Customer.xml", "1", "Johny");
The name "Mark" will have changed in  the XML document to "Johny"


TRy this and let me know.
Jitendra Faye replied to Hafiz Ullah on 23-Nov-11 11:13 PM
Sorry for previous answer.

A sparse matrix is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse n×n matrix with cn entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factorize (with high probability and for large enough c; Gilbert et al. 1992).